[关闭]
@TryMyEdge 2017-02-08T16:22:35.000000Z 字数 6448 阅读 881

专题五(拓扑排序、欧拉路)

题解

题目

A 确定比赛名次

题目大意：

    有N(1<=N<=500)只队伍，M个关系，第i个关系包括两个整数ai和bi(1<=ai，bi<=N)，表示ai队的排名在bi队前面。要求按从前到后的顺序输出榜单，不能确定关系的编号小的队在前。题目保证可以输出一个合法的榜单。
    多组数据。

解题思路：

    裸的拓扑排序。
    因为要求编号小的队伍在前，所以改用优先队列跑拓扑。
    时间复杂度o(n*log(n)+m)，空间复杂度o(n+m)。

AC代码：

  1. #include<iostream>
  2. #include<functional>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<queue>
  6. #include<algorithm>
  7. #include<cstring>
  8. #define pq priority_queue
  9. #define Pi acos(-1.0)
  10. using namespace std;
  11. #define MOD 1000000007
  12. queue <int> q[505];
  13. int deg[505];
  14. pq <int,vector<int>,greater<int> > p;
  15. int main()
  16. {
  17.     int n,m,a,b;
  18.     while(~scanf("%d%d",&n,&m))
  19.     {
  20.         while(m--)
  21.         {
  22.             scanf("%d%d",&a,&b);
  23.             deg[b]++;
  24.             q[a].push(b);
  25.         }
  26.         for(int i=1;i<=n;i++)
  27.         {
  28.             if(deg[i]==0)
  29.                 p.push(i);
  30.         }
  31.         m=0;
  32.         while(!p.empty())
  33.         {
  34.             a=p.top();
  35.             p.pop();
  36.             if(m)
  37.                 printf(" ");
  38.             else
  39.                 m=1;
  40.             printf("%d",a);
  41.             while(!q[a].empty())
  42.             {
  43.                 b=q[a].front();
  44.                 q[a].pop();
  45.                 deg[b]--;
  46.                 if(deg[b]==0)
  47.                     p.push(b);
  48.             }
  49.         }
  50.         printf("\n");
  51.     }
  52.     return 0;
  53. }

B Reward

题目大意：

    有n(n<=10000)个工人，m(m<=20000)个关系，第i个关系包括两个整数ai和bi(1<=ai，bi<=n)，表示ai号工人的奖金要比在bi号工人高。每个人的奖金最少为888元。求一共最少发多少奖金，如果没有合法的方案输出-1。
    多组数据。

解题思路：

    预处理最开始在队列里的那些工人的奖金为888，跑拓扑的时候顺便更新一下每个点的最少工资。记录有多少个点进过队列，如果不足n个则说明有环，没有合法方案。
    时间复杂度o(m+n)，空间复杂度o(m+n)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. queue <int> q[10005],p;
  12. int deg[10005],cost[10005];
  13. int main()
  14. {
  15.     int n,m,a,b;
  16.     int ans;
  17.     while(~scanf("%d%d",&n,&m))
  18.     {
  19.         ans=0;
  20.         for(int i=1;i<=n;i++)
  21.         {
  22.             while(!q[i].empty()) q[i].pop();
  23.             deg[i]=0;
  24.         }
  25.         while(m--)
  26.         {
  27.             scanf("%d%d",&a,&b);
  28.             deg[a]++;
  29.             q[b].push(a);
  30.         }
  31.         memset(cost,0,sizeof(cost));
  32.         for(int i=1;i<=n;i++)
  33.         {
  34.             if(deg[i]==0)
  35.             {
  36.                 p.push(i);
  37.                 cost[i]=888;
  38.             }
  39.         }
  40.         m=0;
  41.         while(!p.empty())
  42.         {
  43.             a=p.front();
  44.             p.pop();
  45.             ans+=cost[a];
  46.             m++;
  47.             while(!q[a].empty())
  48.             {
  49.                 b=q[a].front();
  50.                 q[a].pop();
  51.                 deg[b]--;
  52.                 cost[b]=max(cost[b],cost[a]+1);
  53.                 if(deg[b]==0)
  54.                     p.push(b);
  55.             }
  56.         }
  57.         if(n>m)
  58.             printf("-1\n");
  59.         else
  60.             printf("%d\n",ans);
  61.     }
  62.     return 0;
  63. }

C Rank of Tetris

题目大意：

    有N(0<=N<=10000)个人，M(0<=M<=20000)个关系，第i个关系说明了两个人的rating关系为前者高于后者、两者一样或后者高于前者。两个rating一样的人编号大的排前面。求能不能根据这些信息确定一张榜单，如果不能是因为信息冲突还是因为信息不足。两种原因都有的情况下判断为信息冲突。
    多组数据。

解题思路：

    因为rating一样的人的排名顺序是确定的而且是连续的，所以先用并查集把所有相等关系用并查集处理合并，再用剩下的并查集的根节点跑拓扑。如果某个时刻队列里同时存在超过一个点，则这两个点的顺序是不确定的，所以信息不足。如果有环则说明信息冲突。根据几个标志按题目要求的优先度输出即可。
    小细节：注意处理完合并点数可能已经发生变化，判断信息冲突的时候应该按合并后的点数算。用来跑拓扑的边应该是连在两端点所属并查集的根节点上。
    时间复杂度o(m+n)，空间复杂度o(n+m)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. queue <int> q[10005],p;
  12. int deg[10005];
  13. int root[10005];
  14. int findr(int x)
  15. {
  16.     if(root[x]==x)
  17.         return x;
  18.     else
  19.         return root[x]=findr(root[x]);
  20. }
  21. struct cp
  22. {
  23.     int x,y;
  24. }temp;
  25. queue <cp> mq;
  26. int main()
  27. {
  28.     int n,nt,m,a,b,now;
  29.     char s[6];
  30.     int flag;
  31.     while(~scanf("%d%d",&n,&m))
  32.     {
  33.         nt=n;
  34.         flag=0;
  35.         for(int i=0;i<n;i++)
  36.         {
  37.             root[i]=i;
  38.             while(!q[i].empty()) q[i].pop();
  39.             deg[i]=0;
  40.         }
  41.         while(m--)
  42.         {
  43.             scanf("%d%s%d",&a,s,&b);
  44.             if(s[0]=='=')
  45.             {
  46.                 a=findr(a);
  47.                 b=findr(b);
  48.                 if(a!=b)
  49.                 {
  50.                     root[a]=b;
  51.                     n--;
  52.                 }
  53.             }
  54.             else
  55.             {
  56.                 if(s[0]=='>')
  57.                 {
  58.                     temp.x=a;
  59.                     temp.y=b;
  60.                 }
  61.                 else
  62.                 {
  63.                     temp.x=b;
  64.                     temp.y=a;
  65.                 }
  66.                 mq.push(temp);
  67.             }
  68.         }
  69.         m=0;
  70.         while(!mq.empty())
  71.         {
  72.             temp=mq.front();
  73.             mq.pop();
  74.             temp.x=findr(temp.x);
  75.             temp.y=findr(temp.y);
  76.             deg[temp.x]++;
  77.             q[temp.y].push(temp.x);
  78.         }
  79.         for(int i=0;i<nt;i++)
  80.         {
  81.             if(deg[i]==0 && findr(i)==i)
  82.                 p.push(i);
  83.         }
  84.         while(!p.empty())
  85.         {
  86.             if(p.size()>1)
  87.                 flag=1;
  88.             a=p.front();
  89.             p.pop();
  90.             m++;
  91.             while(!q[a].empty())
  92.             {
  93.                 b=q[a].front();
  94.                 q[a].pop();
  95.                 deg[b]--;
  96.                 if(deg[b]==0)
  97.                     p.push(b);
  98.             }
  99.         }
  100.         if(n>m)
  101.             printf("CONFLICT\n");
  102.         else
  103.         {
  104.             if(flag)
  105.                 printf("UNCERTAIN\n");
  106.             else
  107.                 printf("OK\n");
  108.         }
  109.     }
  110.     return 0;
  111. }

D 欧拉回路

题目大意：

    给定一个N(1<N<=1000)个点、M条边的无向图。问是否存在欧拉回路。
    多组数据。

解题思路：

    欧拉回路结论题。一个无向图有欧拉回路的充要条件：(1)图连通(2)每个点的度都是偶数。
    所以在输入的同时维护每个节点的度，并且用并查集维护连通性即可。
    时间复杂度o(n+m)，空间复杂度o(n)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. int deg[1005];
  12. int root[1005];
  13. int findr(int x)
  14. {
  15.     if(root[x]==x)
  16.         return x;
  17.     else
  18.         return root[x]=findr(root[x]);
  19. }
  20. int main()
  21. {
  22.     int n,m,a,b;
  23.     int flag;
  24.     while(scanf("%d",&n),n)
  25.     {
  26.         scanf("%d",&m);
  27.         flag=1;
  28.         for(int i=1;i<=n;i++)
  29.         {
  30.             root[i]=i;
  31.             deg[i]=0;
  32.         }
  33.         while(m--)
  34.         {
  35.             scanf("%d%d",&a,&b);
  36.             deg[a]++;
  37.             deg[b]++;
  38.             a=findr(a);
  39.             b=findr(b);
  40.             if(a>b)
  41.                 root[a]=b;
  42.             else
  43.                 root[b]=a;
  44.         }
  45.         for(int i=1;i<=n;i++)
  46.         {
  47.             if(root[i]!=1 || deg[i]%2)
  48.                 flag=0;
  49.         }
  50.         printf("%d\n",flag);
  51.     }
  52.     return 0;
  53. }

E Play on Words

题目大意：

    有N(1<=N<=100000)个单词，问是否存在这N个单词的某种排列，满足每个单词的第一个字母和前一个单词的最后一个字母相同。
    T组数据。

解题思路：

    把26个字母看成26个点，每个单词看成起点为首字母终点为尾字母的有向边，题目就转化为判断有向图是否有欧拉路径。
    一个有向图有欧拉路的充要条件：(1)图半连通(2)出度=入度+1的点为潜在起点，入度=出度+1的点为潜在终点，潜在终点和潜在起点都为0或都为1且其余点的出度都等于入度。
    所以在输入的时候维护一下每条边起点出度和终点的入度，同时合并这两个点所属的并查集，最终按照以上两个条件判断即可。
    小细节：26个字母可能只出现了一部分，注意判断。
    时间复杂度o(N)，空间复杂度o(1000)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. int deg1[666],deg2[666];
  12. int root[666];
  13. bool life[666];
  14. char s[1005];
  15. int findr(int x)
  16. {
  17.     if(root[x]==x)
  18.         return x;
  19.     else
  20.         return root[x]=findr(root[x]);
  21. }
  22. int main()
  23. {
  24.     int t,l,m,a,b,gg1,gg2,gg;
  25.     int flag;
  26.     cin>>t;
  27.     while(t--)
  28.     {
  29.         scanf("%d",&m);
  30.         flag=0;
  31.         for(int i='a';i<='z';i++)
  32.         {
  33.             root[i]=i;
  34.             deg1[i]=deg2[i]=0;
  35.             life[i]=0;
  36.         }
  37.         while(m--)
  38.         {
  39.             scanf("%s",s);
  40.             l=strlen(s);
  41.             a=s[0];
  42.             b=s[l-1];
  43.             deg1[a]++;
  44.             deg2[b]++;
  45.             life[a]=1;
  46.             life[b]=1;
  47.             a=findr(a);
  48.             b=findr(b);
  49.             root[a]=b;
  50.             gg=b;
  51.         }
  52.         gg1=gg2=0;
  53.         for(int i='a';i<='z';i++)
  54.         {
  55.             if(deg1[i]!=deg2[i])
  56.             {
  57.                 if(deg1[i]==deg2[i]+1)
  58.                     gg1++;
  59.                 else
  60.                 {
  61.                     if(deg1[i]==deg2[i]-1)
  62.                         gg2++;
  63.                     else
  64.                         flag=1;
  65.                 }
  66.             }
  67.             if(findr(i)!=gg && life[i])
  68.                 flag=1;
  69.         }
  70.         if(gg1>1 || gg2>1 || gg1!=gg2)
  71.             flag=1;
  72.         if(flag)
  73.             printf("The door cannot be opened.\n");
  74.         else
  75.             printf("Ordering is possible.\n");
  76.     }
  77.     return 0;
  78. }

F The Best Path

题目大意：

    有N(N<=100000)个湖，第i个湖的幸运值为ai(0<=ai<=10000)，M(M<=500000)条河，每条河连接两个湖，河是双向的并且有可能连接的湖是同一个。幸运值为一路上经过的所有的湖的幸运值的异或和。问能不能从一个湖出发，经过所有的河，如果能的话求出最大的幸运值。

解题思路：

    判断能不能经过所有的河就是判断图有没有欧拉路。如果存在，并且不是欧拉回路，那么每个点的访问次数都是固定的，为度数的一半，起点和终点各多访问一次。一个数如果异或奇数次那么异或和的值为它本身，如果异或偶数次那么异或和的值为0，并且异或满足交换律。由此可以计算出幸运值。如果是欧拉回路，那么每个点被访问次数为度数的一半，起点和终点为同一个点，会被多访问一次。于是求出剩余点的幸运值之后，枚举起点取最大的幸运值。
    时间复杂度o(n+m)，空间复杂度o(n+m)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<cstring>
  7. #define pq priority_queue
  8. #define Pi acos(-1.0)
  9. using namespace std;
  10. #define MOD 1000000007
  11. int deg[100005];
  12. int root[100005];
  13. int num[100005];
  14. int findr(int x)
  15. {
  16.     if(root[x]==x)
  17.         return x;
  18.     else
  19.         return root[x]=findr(root[x]);
  20. }
  21. int main()
  22. {
  23.     int t,n,m,a,b,gg1,gg2,gg;
  24.     int flag,ans1,ans2;
  25.     cin>>t;
  26.     while(t--)
  27.     {
  28.         scanf("%d%d",&n,&m);
  29.         flag=0;
  30.         ans1=0;
  31.         ans2=0;
  32.         for(int i=1;i<=n;i++)
  33.         {
  34.             root[i]=i;
  35.             deg[i]=0;
  36.             scanf("%d",num+i);
  37.         }
  38.         while(m--)
  39.         {
  40.             scanf("%d%d",&a,&b);
  41.             deg[a]++;
  42.             deg[b]++;
  43.             a=findr(a);
  44.             b=findr(b);
  45.             root[a]=b;
  46.             gg=b;
  47.         }
  48.         m=0;
  49.         for(int i=1;i<=n;i++)
  50.         {
  51.             if((deg[i]/2)%2)
  52.                 ans1^=num[i];
  53.             if(findr(i)!=gg)
  54.                 flag=1;
  55.             if(deg[i]%2)
  56.             {
  57.                 m++;
  58.                 ans2^=num[i];
  59.             }
  60.         }
  61.         if(m!=0 && m!=2)
  62.             flag=1;
  63.         if(flag)
  64.             printf("Impossible\n");
  65.         else
  66.         {
  67.             if(m==2)
  68.                 ans2^=ans1;
  69.             else
  70.             {
  71.                 for(int i=1;i<=n;i++)
  72.                     ans2=max(ans2,ans1^num[i]);
  73.             }
  74.             printf("%d\n",ans2);
  75.         }
  76.     }
  77.     return 0;
  78. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注