[关闭]
@iamtts 2017-02-12T00:14:34.000000Z 字数 2726 阅读 863

寒假第四次训练-并查集&生成树

A - How Many Tables

题目大意：招待客人需要把互相认识放在一桌，给定认识关系，问最少要多少桌

解题思路：并查集，求有多少根

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. using namespace std;
  9. #define MAXN 1005
  11. int par_[MAXN],rank_[MAXN];
  12. bool hash_[MAXN];
  14. void init_(int n)
  15. {
  16.     for (int i=0;i<=n;i++)
  17.     {
  18.         par_[i]=i;
  19.         rank_[i]=0;
  20.     }
  21. }
  22. int find_(int x)
  23. {
  24.     if (par_[x]==x) return x;
  25.     else return par_[x]=find_(par_[x]);
  26. }
  27. void unite_(int x,int y)
  28. {
  29.     x=find_(x);
  30.     y=find_(y);
  31.     if (x==y) return;
  32.     if (rank_[x]<rank_[y])
  33.     {
  34.         par_[x]=y;
  35.     }
  36.     else
  37.     {
  38.         par_[y]=x;
  39.         if (rank_[x]==rank_[y]) rank_[x]++;
  40.     }
  41. }
  42. int main()
  43. {
  44.     int t,a,b,m,n,count_;
  45.     scanf("%d",&t);
  46.     while(t--)
  47.     {
  48.         count_=0;
  49.         fill(hash_,hash_+MAXN,true);
  50.         scanf("%d%d",&n,&m);
  51.         init_(n);
  52.         for (int i=0;i<m;i++)
  53.         {
  54.             scanf("%d%d",&a,&b);
  55.             unite_(a,b);
  56.         }
  57.         for (int i=1;i<=n;i++)
  58.         {
  59.             par_[i]=find_(i);
  60.             if (hash_[par_[i]])
  61.             {
  62.                 count_++;
  63.                 hash_[par_[i]]=false;
  64.             }
  65.         }
  66.         printf("%d\n",count_);
  67.     }
  68. }

B - Corporative Network

题目大意：有n个互相独立的通信中心，有两种指令E和I，I a b表示将a中心连接到b中心，a与b之间距离为|a-b|，于是只剩下新的b中心，E a表示查询a到与之相连的中心的距离

解题思路：并查集，合并时将a并入b所在的集合

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. using namespace std;
  9. #define MAXN 20005
  11. pair<int,int> par_[MAXN];
  13. void init_(int n)
  14. {
  15.     for (int i=0; i<=n; i++)
  16.     {
  17.         par_[i].first=i;
  18.         par_[i].second=0;
  19.     }
  20. }
  21. int find_(int x)
  22. {
  23.     if (par_[x].first==x) return x;
  24.     else
  25.     {
  26.         int parent=find_(par_[x].first);
  27.         par_[x].second+=par_[par_[x].first].second;
  28.         par_[x].first=parent;
  29.         return parent;
  30.     }
  31. }
  32. void unite_(int x,int y)
  33. {
  34.     par_[x].first=y;
  35.     par_[x].second+=abs(x-y)%1000;
  36. }
  37. int main()
  38. {
  39.     int t,a,b,n;
  40.     char ch;
  41.     scanf("%d",&t);
  42.     while(t--)
  43.     {
  44.         scanf("%d",&n);
  45.         init_(n);
  46.         while (getchar(),(ch=getchar())!='O')
  47.         {
  48.             if (ch=='I')
  49.             {
  50.                 scanf("%d%d",&a,&b);
  51.                 unite_(a,b);
  52.             }
  53.             if (ch=='E')
  54.             {
  55.                 scanf("%d",&a);
  56.                 find_(a);
  57.                 printf("%d\n",par_[a].second);
  58.             }
  59.         }
  60.     }
  61. }

C - 卿学姐与诡异村庄

题目大意：村庄有n人，村民有好有坏，好人说真话，坏人说假话，第i人会说某个人是好人或者坏人，问是否存在某个好人坏人的分类使得所有质控都被满足

解题思路：并查集分为两段好人n人坏人n人，i说ai为好人则i与ai要么都为好人要么都为坏人，所以合并i与ai，i+n与ai+n，i说ai为坏人则i好ai坏或者i坏ai好，合并i与ai+n还有i+n与ai。若存在合理分类那么对于任意i，i与i+n是相反的。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. using namespace std;
  9. #define MAXN 100005
  11. int par[MAXN<<1],rank_[MAXN<<1];
  12. //pair<int,int> a[MAXN];
  14. void init_(int n)
  15. {
  16.     for (int i=0; i<=n; i++)
  17.     {
  18.         par[i]=i;
  19.         rank_[i]=0;
  20.     }
  21. }
  22. int find_(int n)
  23. {
  24.     if (par[n]==n) return n;
  25.     else
  26.         return  par[n]=find_(par[n]);
  27. }
  28. bool same(int x,int y)
  29. {
  30.     return find_(x)==find_(y);
  31. }
  32. void unite_(int x,int y)
  33. {
  34.     int m=find_(x),n=find_(y);
  35.     if (m==n) return;
  37.     if (rank_[m]<rank_[n])
  38.         par[m]=n;
  39.     else
  40.     {
  41.         par[n]=m;
  42.         if (rank_[m]==rank_[n]) rank_[m]++;
  43.     }
  44. }
  45. int main()
  46. {
  47.     int t,a,b,n,ai,flag=0;
  49.     while(~scanf("%d",&n))
  50.     {
  51.         flag=0;
  52.         init_(n<<1);
  53.         for (int i=1; i<=n; i++)
  54.         {
  55.             scanf("%d%d",&ai,&t);
  56.             if (t==1)
  57.             {
  58.                 unite_(i,ai);
  59.                 unite_(i+n,ai+n);
  60.             }
  61.             if (t==2)
  62.             {
  63.                 unite_(i,ai+n);
  64.                 unite_(i+n,ai);
  65.             }
  66.         }
  67.         for (int i=1; i<=n; i++)
  68.         {
  69.             if (find_(i)==find_(i+n))
  70.             {
  71.                 flag=1;
  72.                 printf("One face meng bi\n");
  73.                 break;
  74.             }
  75.         }
  76.         if (flag==0) printf("Time to show my power\n");
  77.     }
  79. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注