Codeforces 776D The Door Problem

题目链接：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}$属于一个连通块就无解了，因为包含关系成环。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 2001000

 #define llg int

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,fa[maxn],k,c[maxn];

 llg a[maxn][];

 llg find(llg x) {if (fa[x]!=x)  fa[x]=find(fa[x]); return fa[x];}

 void link(llg x,llg y)

 {

     llg f1=find(x),f2=find(y);

     if (f2!=f1) fa[f2]=f1;

 }

 int main()

 {

     yyj("D");

     cin>>n>>m;

     for (llg i=;i<=n;i++) scanf("%d",&c[i]);

     for (llg i=;i<=m*;i++) fa[i]=i;

     for (llg j=;j<=m;j++)

     {

         cin>>k;

         llg x;

         for (llg i=;i<=k;i++)

         {

             scanf("%d",&x);

             a[x][++a[x][]]=j;

         }

     }

     for (llg i=;i<=n;i++)

     {

         llg u=a[i][],v=a[i][];

         if (!c[i]) link(u,v+m),link(u+m,v);else link(u,v),link(u+m,v+m);

     }

     for (llg i=;i<=m;i++) if (find(i)==find(i+m)) {cout<<"NO"; return ;}

     cout<<"YES";

     return ;

 }

巴特西

Codeforces 776D The Door Problem

最新文章

热门文章