[关闭]
@iamtts 2017-02-10T15:42:57.000000Z 字数 3897 阅读 976

寒假第五次训练-欧拉回路&拓扑排序

A - 确定比赛名次

题目大意：有n支队伍比赛，已知m组形如：a b的数据，表示a战胜了b，求所有队伍的排名顺序，且序号小的队伍排名在前

解题思路：拓扑排序，需要注意的是在每搜索到一个入度为0的点且削减完与它连接的点的入度就重新循环，保证序号小的在前。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. using namespace std;
  10. #define MAXN 505
  12. int indegree[MAXN],topo[MAXN],n,m;
  13. int G[MAXN][MAXN];
  15. void toposort()
  16. {
  17.     int u,v,i,t=0;
  18.     memset(topo,0,sizeof(topo));
  19.     for (i=0; i<n; i++)
  20.     {
  21.         for (u=1; u<=n; u++)
  22.         {
  23.             if (indegree[u]==0)
  24.             {
  25.                 indegree[u]=-1;
  26.                 topo[t++]=u;
  27.                 for (v=1; v<=n; v++)
  28.                 {
  29.                     if (G[u][v]) indegree[v]--;
  30.                 }
  31.                 break;
  32.             }
  33.         }
  34.     }
  35. }
  36. int main()
  37. {
  38.     int u,v;
  39.     while(~scanf("%d%d",&n,&m))
  40.     {
  41.         memset(G,0,sizeof(G));
  42.         memset(indegree,0,sizeof(indegree));
  43.         for (int i=0; i<m; i++)
  44.         {
  45.             scanf("%d%d",&u,&v);
  46.             if (G[u][v]==0)
  47.             {
  48.                 G[u][v]=1;
  49.                 indegree[v]++;
  50.             }
  51.         }
  53.         toposort();
  55.         for (int i=0; i<n; i++)
  56.             printf("%d%c",topo[i],i==n-1?'\n':' ');
  58.     }
  59. }

B - Reward

题目大意：有n个工人，他们需要从老板那里拿工资，然后提出了m个要求，形如：a b，表示a要求工资比b高，每个人基准工资为888，求老板需支出的最小工资

解题思路：数据较大，用邻接表（vector）存储，a比b工资高则a的入度增加，从入度为0的基准工资（888）开始拓扑排序，最后加和。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. using namespace std;
  10. #define MAXN 10005
  12. int indegree[MAXN],a[MAXN],n,m;
  13. vector<int> G[MAXN];
  14. stack<int> temp;
  16. void toposort()
  17. {
  18.     int u,v,i,t=0,rec=n,sum=0;
  19.     memset(a,0,sizeof(a));
  20.     for (i=0; i<n; i++)
  21.     {
  22.         for (u=1; u<=n; u++)
  23.         {
  24.             if (indegree[u]==0)
  25.             {
  26.                 temp.push(u);
  27.                 indegree[u]=-1;
  28.                 a[u]=i;
  29.                 rec--;
  30.             }
  31.         }
  32.         while (!temp.empty())
  33.         {
  34.             u=temp.top();
  35.             temp.pop();
  36.             for (v=0; v<G[u].size(); v++)
  37.             {
  38.                 indegree[G[u][v]]--;
  39.             }
  40.         }
  41.     }
  43.     if (rec==0)
  44.     {
  45.         for (int i=1;i<=n;i++)
  46.             sum+=a[i];
  47.         printf("%d\n",888*n+sum);
  48.     }
  49.     else
  50.     {
  51.         printf("-1\n");
  52.     }
  53. }
  54. int main()
  55. {
  56.     int u,v;
  57.     while(~scanf("%d%d",&n,&m))
  58.     {
  59.         memset(indegree,0,sizeof(indegree));
  60.         for (int i=0; i<=n; i++)
  61.             G[i].clear();
  62.         for (int i=0; i<m; i++)
  63.         {
  64.             scanf("%d%d",&u,&v);//v比u工资低
  65.             G[v].push_back(u);
  66.             indegree[u]++;
  67.         }
  68.         toposort();
  70.     }
  71. }

D - 欧拉回路

题目大意：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

解题思路：欧拉回路要满足：1.图是联通的；2.每个点连线数为偶数

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. using namespace std;
  10. #define MAXN 1005
  12. int degree[MAXN],n,m;
  13. int G[MAXN][MAXN];
  15. bool judge()
  16. {
  17.     int i,j;
  18.     for (i=1; i<=n; i++)
  19.     {
  20.         if (degree[i]%2!=0) return false;
  21.         for (j=1; j<=n; j++)
  22.         {
  23.             if (i!=j && G[i][j]!=1) return false;
  24.         }
  26.     }
  27.     return true;
  28. }
  29. int main()
  30. {
  31.     int u,v;
  32.     while(scanf("%d",&n),n)
  33.     {
  34.         scanf("%d",&m);
  35.         memset(G,0,sizeof(G));
  36.         memset(degree,0,sizeof(degree));
  37.         for (int i=0; i<m; i++)
  38.         {
  39.             scanf("%d%d",&u,&v);
  40.             if (G[u][v]==0)
  41.             {
  42.                 G[v][u]=G[u][v]=1;
  43.                 degree[v]++;
  44.                 degree[u]++;
  45.             }
  46.         }
  47.         if (judge()) printf("1\n");
  48.         else printf("0\n");
  50.     }
  51. }

E - Play on Words

题目大意：给定n个单词，判断是否可以适当排序使之首尾相连，如：acm与mouse就可以连接

解题思路：单词的首尾字母作为节点，中间部分作为连线，划为欧拉道路问题来解决，用并查集判断是否联通

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  7. #include <cstring>
  8. #include <stack>
  9. using namespace std;
  10. #define MAXN 100005
  12. int indegree[27],outdegree[27],n;
  13. int count_;
  14. int par[27],rank_[27];
  15. bool hash_[27];
  16. void init()
  17. {
  18.     int i;
  19.     for (i=0;i<26;i++)
  20.         par[i]=i;
  21.         rank_[i]=0;
  22. }
  23. int find_(int x)
  24. {
  25.     if (par[x]==x) return x;
  26.     else return  par[x]=find_(par[x]);
  27. }
  28. void unite(int x,int y)
  29. {
  30.     x=find_(x);
  31.     y=find_(y);
  32.     if (x==y) return;
  34.     if (rank_[x]<rank_[y])
  35.         par[x]=y;
  36.     else
  37.     {
  38.         par[y]=x;
  39.         if (rank_[x]==rank_[y]) rank_[x]++;
  40.     }
  41.     count_--;
  42. }
  43. bool judge()
  44. {
  45.     int i,j,rec=0,flag1=0,flag2=0;
  46.     for (i=0;i<26;i++)
  47.     {
  48.         if (indegree[i]!=outdegree[i])
  49.         {
  50.             rec++;
  51.             if (rec>2) return false;
  52.             if (indegree[i]==outdegree[i]+1) flag1=1;
  53.             else if (indegree[i]==outdegree[i]-1) flag2=1;
  54.             else return false;
  55.         }
  56.     }
  57.     if (count_!=1) return false;
  58.     if (rec==0 || (rec==2 && flag1&flag2)) return true;
  59.     else return false;
  60.     return true;
  61. }
  62. int main()
  63. {
  64.     int u,v,t,j;
  65.     int first,last;
  66.     char word[1005];
  67.     scanf("%d",&t);
  68.     while(t--)
  69.     {
  70.         scanf("%d",&n);
  71.         count_=0;
  72.         memset(indegree,0,sizeof(indegree));
  73.         memset(outdegree,0,sizeof(outdegree));
  74.         memset(hash_,true,sizeof(hash_));
  75.         init();
  76.         for (int i=0; i<n; i++)
  77.         {
  78.             scanf("%s",word);
  79.             first=word[0]-97;
  80.             for(j=0;word[j]!='\0';j++);
  81.             last=word[j-1]-97;
  83.             outdegree[first]++;
  84.             indegree[last]++;
  85.             if (hash_[first])
  86.             {
  87.                 hash_[first]=false;
  88.                 count_++;
  89.             }
  90.             if (hash_[last])
  91.             {
  92.                 hash_[last]=false;
  93.                 count_++;
  94.             }
  95.             unite(first,last);
  96.         }
  97.         if (judge()) printf("Ordering is possible.\n");
  98.         else printf("The door cannot be opened.\n");
  100.     }
  101. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注