[关闭]
@ysner 2018-11-07T08:45:03.000000Z 字数 3596 阅读 2108

noip2010关押罪犯

并查集 二分图 二分

居然开始写水题题解了，noip退役预定

题面

戳我

解析

这道题似乎有三种做法：

并查集

我们知道，如果要求两个人不冲突，它们必须在不同监狱里。
然而总共也只有两个监狱啊。
所以对于一个人来说，要么和另一个人在同一监狱，要么和另一人不在同一监狱。
这种二分图式的排斥关系，其实可以用并查集的补集来表示。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  12. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  13. using namespace std;
  14. const int N=1e5+100;
  15. int n,m,f[N];
  16. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  17. struct dat{int u,v,w;il bool operator < (const dat &o) const {return w>o.w;}}a[N];
  18. il ll gi()
  19. {
  20.   re ll x=0,t=1;
  21.   re char ch=getchar();
  22.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23.   if(ch=='-') t=-1,ch=getchar();
  24.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25.   return x*t;
  26. }
  27. il void cmax(re int &x,re int y){x=(x>y?x:y);}
  28. int main()
  29. {
  30.   n=gi();m=gi();
  31.   fp(i,1,n*2) f[i]=i;
  32.   fp(i,1,m)
  33.     {
  34.       re int u=gi(),v=gi(),w=gi();
  35.       a[i]=(dat){u,v,w};
  36.     }
  37.   sort(a+1,a+1+m);
  38.   fp(i,1,m)
  39.     {
  40.       re int u=a[i].u,v=a[i].v,w=a[i].w,fu=find(u),fv=find(v);
  41.       if(fu==fv) return printf("%d\n",w),0;
  42.       f[fu]=find(v+n);f[fv]=find(u+n);
  43.     }
  44.   puts("0");
  45.   return 0;
  46. }

二分图染色

仔细看看题，你会发现，要求的其实是最小化的最大值。
这种问题可以二分。

于是只连权值大于的边。
然后判断所有边的两端是否能去不同的监狱。
这个可以用二分图染色完成。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  12. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  13. using namespace std;
  14. const int N=1e5+100;
  15. int n,m,h[N],cnt,col[N],tag;
  16. struct Edge{int to,nxt;}e[N<<1];
  17. struct dat{int u,v,w;il bool operator < (const dat &o) const {return w>o.w;}}a[N];
  18. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  19. il ll gi()
  20. {
  21.   re ll x=0,t=1;
  22.   re char ch=getchar();
  23.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24.   if(ch=='-') t=-1,ch=getchar();
  25.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26.   return x*t;
  27. }
  28. il void dfs(re int u)
  29. {
  30.   if(!tag) return;
  31.   for(re int i=h[u];i+1;i=e[i].nxt)
  32.     {
  33.       re int v=e[i].to;
  34.       if(col[v]==-1) col[v]=col[u]^1,dfs(v);
  35.       else if(col[v]==col[u]) {tag=0;return;}
  36.     }
  37. }
  38. il int check(re int x)
  39. {
  40.   memset(h,-1,sizeof(h));cnt=0;memset(col,-1,sizeof(col));
  41.   fp(i,1,m)
  42.     if(a[i].w>x) add(a[i].u,a[i].v),add(a[i].v,a[i].u);
  43.   tag=1;
  44.   fp(i,1,n) if(col[i]==-1) col[i]=0,dfs(i);
  45.   return tag;
  46. }
  47. il void cmax(re int &x,re int y){x=(x>y?x:y);}
  48. int main()
  49. {
  50.   n=gi();m=gi();
  51.   fp(i,1,m)
  52.     {
  53.       re int u=gi(),v=gi(),w=gi();
  54.       a[i]=(dat){u,v,w};
  55.     }
  56.   sort(a+1,a+1+m);
  57.   re int l=0,r=a[1].w,ans=0;
  58.   while(l<=r)
  59.     {
  60.       re int mid=l+r>>1;
  61.       if(check(mid)) ans=mid,r=mid-1;
  62.       else l=mid+1;
  63.     }
  64.   printf("%d\n",ans);
  65.   return 0;
  66. }

二分图

众所周知，要形成二分图，图中不能有奇环。
所以我们把边按边权排序后，只要一条边加入后形成了奇环，就可以输出答案了。

所以怎么判呢？
判是否形成环可以用并查集，判形成的环是否是奇环当然也可以用并查集。

因为每次连边，我们都是把并差集的根结点相连。
如果在之前根结点已经相连，再连边就会形成环。
环的大小吗，就是两端点分别离根结点的距离之和。（当然不能路径压缩）

所以每次合并时，我们维护一下每个点到其并查集父亲距离的奇偶性。
求环大小时，从两端点分别暴跳父亲即可。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define pc(a) putchar(a)
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=2e5+100,inf=1e9+100;
  15. int f[N],n,m,dp[N],h[N];
  16. bool vis[N];
  17. ll ans;
  18. struct dat{int u,v,w;bool operator < (const dat &o) const {return w>o.w;}}a[N<<1];
  19. il int find(re int x){while(f[x]^x) x=f[x];return x;}
  20. il int Dis(re int x){re int res=0;while(f[x]^x) res^=dp[x],x=f[x];return res;}
  21. il int gi()
  22. {
  23.   re int x=0,t=1;
  24.   re char ch=getchar();
  25.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26.   if(ch=='-') t=-1,ch=getchar();
  27.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28.   return x*t;
  29. }
  30. int main()
  31. {
  32.   n=gi();m=gi();
  33.   fp(i,1,n) f[i]=i,h[i]=1;
  34.   fp(i,1,m) a[i].u=gi(),a[i].v=gi(),a[i].w=gi();
  35.   sort(a+1,a+1+m);
  36.   fp(i,1,m)
  37.     {
  38.       re int u=a[i].u,v=a[i].v,fu=find(u),fv=find(v),w=a[i].w;
  39.       if(fu^fv) dp[fu]^=Dis(u)^Dis(v)^1,f[fu]=fv;
  40.       else if(Dis(u)^Dis(v)==0) {printf("%d\n",w);return 0;}
  41.     }
  42.   puts("0");
  43.   return 0;
  44. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注