题目链接:http://codeforces.com/contest/776/problem/D
把每一个钥匙拆成两个点${x,x+m}$,分别表示选不选这把钥匙。
我们知道一扇门一定对应了两把钥匙。
设一扇门对应的要是分别为$u,v$,${link(x,y)}$表示点$x$向点$y$连边。
如果这扇门要操作一次,那就是两把当中选一把:${link(u,v+m),link(v,u+m)}$。这表示的是如果我选了拿第$u$把钥匙就不能拿第$v$把钥匙,如果我选了拿第$v$把钥匙就不能拿第$u$把钥匙
如果这扇门不要操作,那就是两把当中选两把或者都不选:${link(u+m,v+m),link(v,u)}$。这表示的是如果我选了拿第$u$把钥匙就一定要拿第$v$把钥匙,如果我不拿第$v$把钥匙就一定不能拿第$u$把钥匙
这个是无向边啊,并查集维护一下关系即可。
对于${1...m}$中的每一把钥匙,如果${x,x+m}$属于一个连通块就无解了,因为包含关系成环。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 2001000 10 #define llg int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,fa[maxn],k,c[maxn]; 13 14 llg a[maxn][4]; 15 16 llg find(llg x) {if (fa[x]!=x) fa[x]=find(fa[x]); return fa[x];} 17 18 void link(llg x,llg y) 19 { 20 llg f1=find(x),f2=find(y); 21 if (f2!=f1) fa[f2]=f1; 22 } 23 24 int main() 25 { 26 yyj("D"); 27 cin>>n>>m; 28 for (llg i=1;i<=n;i++) scanf("%d",&c[i]); 29 for (llg i=1;i<=m*3;i++) fa[i]=i; 30 for (llg j=1;j<=m;j++) 31 { 32 cin>>k; 33 llg x; 34 for (llg i=1;i<=k;i++) 35 { 36 scanf("%d",&x); 37 a[x][++a[x][0]]=j; 38 } 39 } 40 for (llg i=1;i<=n;i++) 41 { 42 llg u=a[i][1],v=a[i][2]; 43 if (!c[i]) link(u,v+m),link(u+m,v);else link(u,v),link(u+m,v+m); 44 } 45 for (llg i=1;i<=m;i++) if (find(i)==find(i+m)) {cout<<"NO"; return 0;} 46 cout<<"YES"; 47 return 0; 48 }