首页 > 其他分享 >codeforces 505B B. Mr. Kitayuta's Colorful Graph(bfs)

codeforces 505B B. Mr. Kitayuta's Colorful Graph(bfs)

时间:2023-04-23 21:34:08浏览次数:57  
标签:Colorful int Graph ++ d% codeforces vis MAX include


题目链接:

codeforces 505B


题目大意:

给出一个有向图,边有不同的颜色,任意给出查询,查询两点能够只通过一种颜色连通的颜色的种类数。


题目分析:

根据不同颜色建边,bfs即可,队列维护可用的点。


AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 107

using namespace std;

int n,m,c,x,y,q;
vector<int> e[MAX][MAX];
bool vis[MAX];

void add ( int u , int v , int w )
{
    e[w][u].push_back ( v );
    e[w][v].push_back ( u );
}

bool bfs ( int c )
{
    memset ( vis , 0 , sizeof ( vis ) );
    queue<int> q;
    q.push ( x );
    while ( !q.empty() )
    {
        int u = q.front();
        if ( u == y ) return true;
        q.pop();
        for ( int i = 0 ; i < e[c][u].size() ; i++ )
        {
            int v = e[c][u][i];
            if ( vis[v] ) continue;
            vis[v] = true;
            q.push ( v );
        }
    }
    return false;
}

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &m ) )
    {
        for ( int i = 0 ; i < MAX ; i++ )
            for ( int j = 0 ; j < MAX ; j++ )
                e[i][j].clear();
        for ( int i = 0 ; i < m ; i++ )
        {
            scanf ( "%d%d%d" , &x , &y , &c );
            add ( x , y , c );
        }
        scanf ( "%d" , &q );
        while ( q-- )
        {
            int ans = 0;
            scanf ( "%d%d" , &x , &y );
            for ( int i = 1 ; i <= m ; i++ )
                if ( bfs ( i ) ) ans++;
            printf ( "%d\n" , ans );
        }
    }
}


标签:Colorful,int,Graph,++,d%,codeforces,vis,MAX,include
From: https://blog.51cto.com/u_7936627/6218751

相关文章

  • codeforces 332B B. Maximum Absurdity(rmq)
    题目链接:codeforces332B题目大意:给出一个序列,让找出不互相覆盖的两个长度为k的段,问在两个段的权值和最大的情况下,按照左边段的左端点排序,右边段的左端点作为第二关键字排序,得到的第一个答案。题目分析:很水的数据结构的题目,我们只需要先利用前缀和预处理出所有长度为k的段的总权值......
  • codeforces 234C C. Weather(枚举+前缀后缀预处理)
    题目链接:codeforces234C题目大意:给出一个序列,问最少修改多少个元素,能保证前半截全是负数,后半截全是正数。题目分析:预处理出前缀中大于等于0的数的个数和后缀中小于等于0的数的个数。枚举每一个位置,判断以当前位置为分界点时需要修改的元素的个数。AC代码:#include<iostream>#inc......
  • codeforces 172B B. Pseudorandom Sequence Period(暴力)
    题目链接:codeforces172B题目大意:给出生成元,和递推式,求一个有限群元素的个数题目分析:暴力求取循环节即可,因为元素个数不会超过mod的大小,所以暴力法复杂度仅仅是O(105)AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cstdio>#de......
  • codeforces 368B B. Sereja and Suffixes(树状数组)
    题目链接:codeforces368B题目大意:给出一个长度为n的序列a,给出m个查询l,对于每个查询输出[l,n]的区间内不同数的个数。题目分析:将查询按照l的大小排序,从大到小的遍历,每次将>=当前l的位置的a[i]全部加入树状数组,树状数组记录每个数是否出现过。每次结果就是查询树状数组的总和,要保证......
  • codeforces 414B B. Mashmokh and ACM(dp)
    题目链接:codeforces414B题目大意:定义一个序列,前一项能够整除后一项,给定这个序列中数的取值范围和序列的长度,问有多少种构造方法。题目分析:我们定义状态dp[i][j]为前i项已经确定且第i项为j的方案数。转移方程dp[i][j]=∑k|jdp[i−1][k]复杂度O(n⋅k)AC代码:#include<iostream>......
  • codeforces 573B B. Bear and Blocks(线段树+dp)
    题目链接:codeforces573B题目大意:给出n个连续塔,每个塔有高度hi,每次取走最外层的块,问需要多少次操作能够拿光所有的块。题目分析:首先我们可以知道第一次操作时,对于每个塔的变化满足如下的公式:hi=min(hi−1,hi−1,hi+1)每次操作都满足如下的递推式,我们递推一下得到第k次操作第i......
  • codeforces 267A A. Subtractions(辗转相除)
    题目链接:codeforces267A题目大意:给出一个数对,(a,b)每次用较大的减较小的,直到出现0为止,问要进行多少次操作。题目分析:大的减小的操作,可以利用取模优化过程,也就是辗转相除,商是操作次数,余数是下一段与之前较小的数继续进行操作的数,水题不做赘述。AC代码:#include<iostream>#include......
  • codeforces 225B B. Well-known Numbers(数论+二分+贪心+构造)
    题目链接:codeforces225B题目大意:定义f(k,n)为类似菲波那契数推导,只不过变为前k项的和,然后给出一个数s,利用k-菲波那契数构造出一个不重复的集合的元素和为s,集合的规模大于1题目分析:首先因为菲波那契数的增长速度快的吓人,所以给的数据范围109很快就能达到,我们得到O(n)的构造出所有的......
  • 图(Graph)与图论
    听到图这个字,很多人会联想到图片、折线图、设计图等传统的图,今天要聊的图(Graph)是一种基本研究对象,用于表示实体与实体之间的关系。先说结论:图论:是组合数学分支,是主要研究图的学问,起源于柯尼斯堡七桥问题。图(数学):是用于表示物体与物体之间存在某种关系的结构。数学......
  • Quasi Binary---codeforces
    #QuasiBinary##题面翻译**题目描述**给出一个数n,你需要将n写成若干个数的和,其中每个数的十进制表示中仅包含0和1。问最少需要多少个数**输入输出格式**输入格式:一行一个数n(1≤n≤10^6)输出格式:最少的数的个数,并给出一种方案。##题目描述Anumberiscalledquasib......