企业官网建设流程全解析

P11640 Graph

题目背景

hack 数据已添加，位于 Subtask#5，不计分。

题目描述

有一张nnn个点的图，每个点可以是黑色或白色的。

有mmm条限制，第iii条限制会给定ai,bi,cia_i,b_i,c_iai​,bi​,ci​，表示ai⇒bia_i\Rightarrow b_iai​⇒bi​需要有一条长度为cic_ici​的路径，路径可以重复经过某条边或点。

问是否存在一个若干条边权为111有向边的图，满足：

• 满足上述mmm个条件。
• 假如这张图有kkk条边，则对于每个∀1≤i≤k\forall 1\le i\le k∀1≤i≤k，设第iii条边是由uiu_iui​指向viv_ivi​的，那么uiu_iui​的颜色与viv_ivi​的不同。

输入格式

第一行一个整数TTT，表示数据的组数。

对于每组数据，第一行两个整数n,mn,mn,m。

接下来mmm行，每行三个整数，分别为ai,bi,cia_i,b_i,c_iai​,bi​,ci​。

输出格式

TTT行，每行一个字符串s∈{Yes,No}s\in\{\tt{Yes},\tt{No}\}s∈{Yes,No}。

第iii行表示第iii个问题的答案。

输入输出样例 #1

输入 #1

1 5 4 1 3 4 4 2 7 4 4 0 5 2 1

输出 #1

Yes

说明/提示

【样例解释】

可以构造出

以满足要求。

【数据范围】

本题采用捆绑测试。

• Subtask #1（5pts5\text{pts}5pts）：m=0m=0m=0。
• Subtask #2（20pts20\text{pts}20pts）：n≤10n\le 10n≤10。
• Subtask #3（25pts25\text{pts}25pts）：n≤103n\le 10^3n≤103。
• Subtask #4（50pts50\text{pts}50pts）：无特殊限制。

对于100%100\%100%的数据，1≤T≤101\le T\le 101≤T≤10，1≤n≤1061\le n\le 10^61≤n≤106，0≤m≤1060\le m\le 10^60≤m≤106，1≤ai,bi≤n1\le a_i,b_i\le n1≤ai​,bi​≤n，0≤ci≤1090\le c_i\le 10^90≤ci​≤109。

C++实现

#include<bits/stdc++.h>#defineN2000005#definexfirst#defineysecondusingnamespacestd;intT=1,n,m,fa[N];intfind(intx){returnfa[x]==x?x:fa[x]=find(fa[x]);}voidsolve(intcs){cin>>n>>m;for(inti=1;i<=n*2;i++){fa[i]=i;}boolf=1;for(inti=1;i<=m;i++){inta,b,c;cin>>a>>b>>c;if(a!=b&&c==0)f=0;if(n==1&&c!=0)f=0;if(!f)continue;if(c%2==0){if(find(a+n)==find(b)||find(a)==find(b+n)){f=0;continue;}fa[find(a)]=find(b);fa[find(a+n)]=find(b+n);}else{if(find(a)==find(b)||find(a+n)==find(b+n)){f=0;continue;}fa[find(a+n)]=find(b);fa[find(a)]=find(b+n);}}if(n==1){if(f)cout<<"Yes\n";elsecout<<"No\n";return;}intx=find(1);boolg=0;for(inti=1;i<=n;i++){if(find(i)!=x){g=1;break;}}f&=g;if(f)cout<<"Yes\n";elsecout<<"No\n";}signedmain(){cin>>T;for(intcs=1;cs<=T;cs++){solve(cs);}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容