[关闭]
@CQUPTacm 2017-03-17T12:44:26.000000Z 字数 13552 阅读 1319

萌新集中营第二期

题解

题目

A Agri-Net (POJ - 1258)

题意：

    有N个农场(3<=N<=100)，给出一个邻接矩阵表示农场之间的距离，两个农场之间的双向距离是相同的，距离不超过100000。在两个农场之间修一条双向路的代价等于这两个的距离。问将所有农场联通起来的最小代价是多少。
    多组数据。

题解：

    把距离作为边的权值，这道题就变成让我们求最小生成树的总权值。
    最小生成树一般常用prim和kruskal这两种做法。
    prim时间复杂度o(N^2)，空间复杂度o(N^2)。
    kruskal时间复杂度o(N^2*log(n^2))，空间复杂度o(N^2)。

代码：

prim：

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. #define INF 666666
  5. bool life[105];
  6. int val[105];
  7. int n,dis[105][105],ans;
  8. int main()
  9. {
  10.     int u,v,m,now;
  11.     val[0]=INF;
  12.     while(~scanf("%d",&n))
  13.     {
  14.         ans=0;
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             life[i]=0;
  18.             val[i]=INF;
  19.             for(int j=1;j<=n;j++)
  20.                 scanf("%d",&dis[i][j]);
  21.         }
  22.         val[1]=0;
  23.         m=n;
  24.         while(m--)
  25.         {
  26.             now=0;
  27.             for(int i=1;i<=n;i++)
  28.             {
  29.                 if(!life[i] && val[i]<val[now])
  30.                     now=i;
  31.             }
  32.             ans+=val[now];
  33.             life[now]=1;
  34.             for(int j=1;j<=n;j++)
  35.                 val[j]=min(val[j],dis[now][j]);
  36.         }
  37.         printf("%d\n",ans);
  38.     }
  39.     return 0;
  40. }

kruskal:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Edge
  6. {
  7.     int u,v,dis;
  8. }e[10005];
  9. bool cmp(Edge x1,Edge x2)
  10. {
  11.     return x1.dis<x2.dis;
  12. }
  13. int root[105],nums,n,ans;
  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 u,v;
  24.     while(~scanf("%d",&n))
  25.     {
  26.         ans=0;
  27.         nums=0;
  28.         for(int i=1;i<=n;i++)
  29.         {
  30.             root[i]=i;
  31.             for(int j=1;j<=n;j++)
  32.             {
  33.                 e[nums].u=i;
  34.                 e[nums].v=j;
  35.                 scanf("%d",&e[nums].dis);
  36.                 nums++;
  37.             }
  38.         }
  39.         sort(e,e+nums,cmp);
  40.         for(int i=0;i<nums;i++)
  41.         {
  42.             u=findr(e[i].u);
  43.             v=findr(e[i].v);
  44.             if(u!=v)
  45.             {
  46.                 root[u]=v;
  47.                 ans+=e[i].dis;
  48.             }
  49.         }
  50.         printf("%d\n",ans);
  51.     }
  52.     return 0;
  53. }

B Highways (POJ - 2485)

题意：

    有N(3<=N<=500)个村庄，给出一个邻接矩阵表示村庄之间的路的长度，路是双向的，长度在[1，65536]范围内。求要把所有的村庄通过路连起来，最长的路的长度。
    多组数据。

题解：

    这题要我们做的事其实就是尽量用短的路看能不能联通所有村庄，如果不能连起来就继续用路。其实就是kruskal的做法。
    因为kruskal能做，所以prim生成的生成树上最长的边也是答案。
    kruskal时间复杂度o(N^2*log(n^2))，空间复杂度o(N^2)。
    prim时间复杂度o(N^2)，空间复杂度o(N^2)。

代码：

kruskal：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Edge
  6. {
  7.     int u,v,dis;
  8. }e[250005];
  9. bool cmp(Edge x1,Edge x2)
  10. {
  11.     return x1.dis<x2.dis;
  12. }
  13. int root[505],nums,n,ans;
  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 u,v,T;
  24.     scanf("%d",&T);
  25.     while(T--)
  26.     {
  27.         scanf("%d",&n);
  28.         ans=0;
  29.         nums=0;
  30.         for(int i=1;i<=n;i++)
  31.         {
  32.             root[i]=i;
  33.             for(int j=1;j<=n;j++)
  34.             {
  35.                 e[nums].u=i;
  36.                 e[nums].v=j;
  37.                 scanf("%d",&e[nums].dis);
  38.                 nums++;
  39.             }
  40.         }
  41.         sort(e,e+nums,cmp);
  42.         for(int i=0;i<nums;i++)
  43.         {
  44.             u=findr(e[i].u);
  45.             v=findr(e[i].v);
  46.             if(u!=v)
  47.             {
  48.                 root[u]=v;
  49.                 ans=max(ans,e[i].dis);
  50.             }
  51.         }
  52.         printf("%d\n",ans);
  53.     }
  54.     return 0;
  55. }

prim:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. #define INF 666666
  5. bool life[505];
  6. int val[505];
  7. int n,dis[505][505],ans;
  8. int main()
  9. {
  10.     int u,v,m,now,T;
  11.     val[0]=INF;
  12.     scanf("%d",&T);
  13.     while(T--)
  14.     {
  15.         scanf("%d",&n);
  16.         ans=0;
  17.         for(int i=1;i<=n;i++)
  18.         {
  19.             life[i]=0;
  20.             val[i]=INF;
  21.             for(int j=1;j<=n;j++)
  22.                 scanf("%d",&dis[i][j]);
  23.         }
  24.         val[1]=0;
  25.         m=n;
  26.         while(m--)
  27.         {
  28.             now=0;
  29.             for(int i=1;i<=n;i++)
  30.             {
  31.                 if(!life[i] && val[i]<val[now])
  32.                     now=i;
  33.             }
  34.             ans=max(ans,val[now]);
  35.             life[now]=1;
  36.             for(int j=1;j<=n;j++)
  37.                 val[j]=min(val[j],dis[now][j]);
  38.         }
  39.         printf("%d\n",ans);
  40.     }
  41.     return 0;
  42. }

C 继续畅通工程 (HDU - 1879)

题意：

    中文题。。。

题解：

    如果不考虑路的修建状况，这题就是求最小生成树的总权值。
    如果路已经修建完成，那么相当于这条路的代价为0。将所有建好的路的权值改为0，跑最小生成树求总权值即可。

代码：

prim：

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. #define INF 666666
  5. bool life[105];
  6. int val[105];
  7. int n,dis[105][105],ans;
  8. int main()
  9. {
  10.     int u,v,m,now,flag;
  11.     val[0]=INF;
  12.     while(scanf("%d",&n),n)
  13.     {
  14.         ans=0;
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             life[i]=0;
  18.             dis[i][i]=0;
  19.             val[i]=INF;
  20.         }
  21.         m=n*(n-1)/2;
  22.         for(int i=0;i<m;i++)
  23.         {
  24.             scanf("%d%d%d%d",&u,&v,&now,&flag);
  25.             if(flag)
  26.                 dis[u][v]=dis[v][u]=0;
  27.             else
  28.                 dis[u][v]=dis[v][u]=now;
  29.         }
  30.         val[1]=0;
  31.         m=n;
  32.         while(m--)
  33.         {
  34.             now=0;
  35.             for(int i=1;i<=n;i++)
  36.             {
  37.                 if(!life[i] && val[i]<val[now])
  38.                     now=i;
  39.             }
  40.             ans+=val[now];
  41.             life[now]=1;
  42.             for(int j=1;j<=n;j++)
  43.                 val[j]=min(val[j],dis[now][j]);
  44.         }
  45.         printf("%d\n",ans);
  46.     }
  47.     return 0;
  48. }

kruskal:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Edge
  6. {
  7.     int u,v,dis;
  8. }e[10005];
  9. bool cmp(Edge x1,Edge x2)
  10. {
  11.     return x1.dis<x2.dis;
  12. }
  13. int root[105],nums,n,ans;
  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 u,v,now;
  24.     while(scanf("%d",&n),n)
  25.     {
  26.         ans=0;
  27.         nums=n*(n-1)/2;
  28.         for(int i=1;i<=n;i++)
  29.             root[i]=i;
  30.         for(int i=0;i<nums;i++)
  31.         {
  33.             scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].dis,&now);
  34.             if(now)
  35.                 e[i].dis=0;
  36.         }
  37.         sort(e,e+nums,cmp);
  38.         for(int i=0;i<nums;i++)
  39.         {
  40.             u=findr(e[i].u);
  41.             v=findr(e[i].v);
  42.             if(u!=v)
  43.             {
  44.                 root[u]=v;
  45.                 ans+=e[i].dis;
  46.             }
  47.         }
  48.         printf("%d\n",ans);
  49.     }
  50.     return 0;
  51. }

D Genealogical tree (POJ - 2367)

题意：

    有N(1<=N<=100)个火星人，给出他们每个人的后代信息，求一种发言顺序，在每个人发一次言的情况下保证每个人发言的时候自己的后代都还没发言。题目保证至少有一种合法的发言顺序。

题解：

    当一个人的祖先都发过言了，这个人就可以发言了，同时他的所有后代的未发言祖先都要扣掉他。每次找出没有未发言祖先的人让他发言即可。保证祖先在后代之前，这实际上就是一个求拓扑序列的过程。
    时间复杂度o(N^2)，空间复杂度o(N^2)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666666
  6. int fa[105],n;
  7. queue <int> son[105],q;
  8. int main()
  9. {
  10.     int now,temp;
  11.     bool flag=0;
  12.     scanf("%d",&n);
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         while(scanf("%d",&now),now)
  16.         {
  17.             son[i].push(now);
  18.             fa[now]++;
  19.         }
  20.     }
  21.     for(int i=1;i<=n;i++)
  22.     {
  23.         if(fa[i]==0)
  24.             q.push(i);
  25.     }
  26.     while(!q.empty())
  27.     {
  28.         now=q.front();
  29.         q.pop();
  30.         if(!flag)
  31.             flag=1;
  32.         else
  33.             printf(" ");
  34.         printf("%d",now);
  35.         while(!son[now].empty())
  36.         {
  37.             temp=son[now].front();
  38.             son[now].pop();
  39.             fa[temp]--;
  40.             if(fa[temp]==0)
  41.                 q.push(temp);
  42.         }
  43.     }
  44.     printf("\n");
  45.     return 0;
  46. }

E 排名表 (UESTC - 1150)

题意：

    中文题。

题解：

    忽略让排名小的排在前面这个规则，这题就是求拓扑序列。
    判断拓扑序列是否存在的方法，就是判断有没有环。如果有环的话，环上的点肯定都不能进队列，所以我们只需要看一共有多少个点进过队列就行了。
    考虑到要让排名小的排在前面，我们可以反过来想，让序号小的尽可能排后面，最后输出的时候把名次反过来看就行了。为什么要反过来想呢？给出一个例子大家自己思考：3个人，3在1前面，三个人的顺序应该是3、1、2，但是如果让当前序号小的先排，就会变成2、3、1。所以我们把拓扑的关系反过来建，然后用一个大序号排前面的优先队列来代替队列，最后输出的时候把排名反过来看就行了。
    ps：注意初始化。
    时间复杂度o(T*n^2*log(n^2))，空间复杂度o(n^2)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666666
  6. int fa[205],n,ans[205];
  7. queue <int> son[205];
  8. priority_queue <int> q;
  9. int flag;
  10. int main()
  11. {
  12.     int m,now,temp,T,u,v;
  13.     scanf("%d",&T);
  14.     while(T--)
  15.     {
  16.         flag=0;
  17.         scanf("%d%d",&n,&m);
  18.         while(m--)
  19.         {
  20.             scanf("%d%d",&u,&v);
  21.             fa[u]++;
  22.             son[v].push(u);
  23.         }
  24.         for(int i=1;i<=n;i++)
  25.         {
  26.             if(fa[i]==0)
  27.                 q.push(i);
  28.         }
  29.         while(!q.empty())
  30.         {
  31.             now=q.top();
  32.             q.pop();
  33.             flag++;
  34.             ans[now]=flag;
  35.             while(!son[now].empty())
  36.             {
  37.                 temp=son[now].front();
  38.                 son[now].pop();
  39.                 fa[temp]--;
  40.                 if(fa[temp]==0)
  41.                     q.push(temp);
  42.             }
  43.         }
  44.         if(flag==n)
  45.         {
  46.             for(int i=1;i<=n;i++)
  47.             {
  48.                 if(i>1)
  49.                     printf(" ");
  50.                 printf("%d",n+1-ans[i]);
  51.             }
  52.             printf("\n");
  53.         }
  54.         else
  55.         {
  56.             for(int i=1;i<=n;i++)
  57.             {
  58.                 fa[i]=0;
  59.                 while(!son[i].empty())
  60.                 {
  61.                     son[i].pop();
  62.                 }
  63.             }
  64.             printf("-1\n");
  65.         }
  66.     }
  67.     return 0;
  68. }

F 畅通工程续 (HDU - 1874)

题意：

    中文题。

题解：

    题目求的是S和T之间的最短路，可以转化成S到任意点的最短路，然后看S到T的距离。
    单源最短路一般有Dijkstra(优先队列优化)和spfa(队列优化的Bellman-Ford)两种算法。
    Dijkstra的时间复杂度为o(M*log(M))，空间复杂度为o(M)。
    spfa的时间复杂度为o(k*M)，空间复杂度为o(M)。

代码：

Dijkstra：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. struct Edge
  6. {
  7.     int to,dis;
  8.     friend bool operator <(Edge x1,Edge x2)
  9.     {
  10.         return x1.dis>x2.dis;
  11.     }
  12. }temp;
  13. int n,dis[205];
  14. bool life[205];
  15. priority_queue <Edge> pq;
  16. vector <Edge> vec[205];
  17. int main()
  18. {
  19.     int m,u,v,s,t;
  20.     while(~scanf("%d%d",&n,&m))
  21.     {
  22.         for(int i=0;i<n;i++)
  23.         {
  24.             vec[i].clear();
  25.             life[i]=0;
  26.         }
  27.         while(m--)
  28.         {
  29.             scanf("%d%d%d",&u,&v,&temp.dis);
  30.             temp.to=v;
  31.             vec[u].push_back(temp);
  32.             temp.to=u;
  33.             vec[v].push_back(temp);
  34.         }
  35.         scanf("%d%d",&s,&t);
  36.         temp.to=s;
  37.         temp.dis=0;
  38.         pq.push(temp);
  39.         while(!pq.empty())
  40.         {
  41.             temp=pq.top();
  42.             pq.pop();
  43.             if(!life[temp.to])
  44.             {
  45.                 u=temp.to;
  46.                 life[u]=1;
  47.                 dis[u]=temp.dis;
  48.                 for(int i=0;i<vec[u].size();i++)
  49.                 {
  50.                     if(!life[vec[u][i].to])
  51.                     {
  52.                         temp.to=vec[u][i].to;
  53.                         temp.dis=vec[u][i].dis+dis[u];
  54.                         pq.push(temp);
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.         if(!life[t])
  60.             printf("-1\n");
  61.         else
  62.             printf("%d\n",dis[t]);
  63.     }
  64.     return 0;
  65. }

spfa:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 20000007
  6. struct Edge
  7. {
  8.     int to,dis;
  9. }temp;
  10. int n,dis[205];
  11. bool life[205];
  12. queue <int> q;
  13. vector <Edge> vec[205];
  14. int main()
  15. {
  16.     int m,u,v,s,t;
  17.     while(~scanf("%d%d",&n,&m))
  18.     {
  19.         for(int i=0;i<n;i++)
  20.         {
  21.             vec[i].clear();
  22.             life[i]=0;
  23.             dis[i]=INF;
  24.         }
  25.         while(m--)
  26.         {
  27.             scanf("%d%d%d",&u,&v,&temp.dis);
  28.             temp.to=v;
  29.             vec[u].push_back(temp);
  30.             temp.to=u;
  31.             vec[v].push_back(temp);
  32.         }
  33.         scanf("%d%d",&s,&t);
  34.         dis[s]=0;
  35.         q.push(s);
  36.         life[s]=1;
  37.         while(!q.empty())
  38.         {
  39.             u=q.front();
  40.             q.pop();
  41.             life[u]=0;
  42.             for(int i=0;i<vec[u].size();i++)
  43.             {
  44.                 if(vec[u][i].dis+dis[u]<dis[vec[u][i].to])
  45.                 {
  46.                     dis[vec[u][i].to]=vec[u][i].dis+dis[u];
  47.                     if(!life[vec[u][i].to])
  48.                     {
  49.                         life[vec[u][i].to]=1;
  50.                         q.push(vec[u][i].to);
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.         if(dis[t]==INF)
  56.             printf("-1\n");
  57.         else
  58.             printf("%d\n",dis[t]);
  59.     }
  60.     return 0;
  61. }

G Tram (POJ - 1847)

题意：

    有N(2<=N<=100)个岔路口，第i个岔路口链接Ki(0<=Ki<=N-1)条轨道通向不同的岔路口，若Ki不为0，则第i个岔路口一开始的方向为它连接的第一条轨道，如果想要从一个岔路口开向他当前没有连接的那条轨道，则需要更改1次这个岔路口的方向。问从A号岔路口到B号岔路口，最少需要改变多少次岔路口的方向。

题解：

    从点i到i默认通往的那个岔路口去，需要0次转向，到i默认之外的其他连接的岔路口去，需要1次转向。所以可以把每个岔路口到默认岔路口的那条边的权值定为0，剩下的边权值定为1，问题就转化成了从A到B的最短距离。
    ps：因为改变最多次的情况是每个岔路口都经过而且每次都改变方向，所以INF只要大于N就行了。
    Dijkstra的时间复杂度为o(sum(K)*log(sum(K)))，空间复杂度为o(sum(K))。
    spfa的时间复杂度为o(k*sum(K))，空间复杂度为o(sum(K))。

代码：

Dijkstra：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666
  6. struct Edge
  7. {
  8.     int to,dis;
  9.     friend bool operator <(Edge x1,Edge x2)
  10.     {
  11.         return x1.dis>x2.dis;
  12.     }
  13. }temp;
  14. int n,dis[105];
  15. bool life[105];
  16. priority_queue <Edge> pq;
  17. vector <Edge> vec[105];
  18. int main()
  19. {
  20.     int u,v,s,t;
  21.     scanf("%d%d%d",&n,&s,&t);
  22.     for(int i=1;i<=n;i++)
  23.     {
  24.         vec[i].clear();
  25.         life[i]=0;
  26.         dis[i]=INF;
  27.         scanf("%d",&u);
  28.         for(int j=0;j<u;j++)
  29.         {
  30.             scanf("%d",&v);
  31.             if(!j)
  32.                 temp.dis=0;
  33.             else
  34.                 temp.dis=1;
  35.             temp.to=v;
  36.             vec[i].push_back(temp);
  37.         }
  38.     }
  39.     temp.to=s;
  40.     temp.dis=0;
  41.     pq.push(temp);
  42.     while(!pq.empty())
  43.     {
  44.         temp=pq.top();
  45.         pq.pop();
  46.         if(!life[temp.to])
  47.         {
  48.             u=temp.to;
  49.             life[u]=1;
  50.             dis[u]=temp.dis;
  51.             for(int i=0;i<vec[u].size();i++)
  52.             {
  53.                 if(!life[vec[u][i].to])
  54.                 {
  55.                     temp.to=vec[u][i].to;
  56.                     temp.dis=vec[u][i].dis+dis[u];
  57.                     pq.push(temp);
  58.                 }
  59.             }
  60.         }
  61.     }
  62.     if(dis[t]==INF)
  63.         printf("-1\n");
  64.     else
  65.         printf("%d\n",dis[t]);
  66.     return 0;
  67. }

spfa：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666
  6. struct Edge
  7. {
  8.     int to,dis;
  9. }temp;
  10. int n,dis[105];
  11. bool life[105];
  12. queue <int> q;
  13. vector <Edge> vec[105];
  14. int main()
  15. {
  16.     int u,v,s,t;
  17.     scanf("%d%d%d",&n,&s,&t);
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         vec[i].clear();
  21.         life[i]=0;
  22.         dis[i]=INF;
  23.         scanf("%d",&u);
  24.         for(int j=0;j<u;j++)
  25.         {
  26.             scanf("%d",&v);
  27.             if(!j)
  28.                 temp.dis=0;
  29.             else
  30.                 temp.dis=1;
  31.             temp.to=v;
  32.             vec[i].push_back(temp);
  33.         }
  34.     }
  35.     dis[s]=0;
  36.     q.push(s);
  37.     life[s]=1;
  38.     while(!q.empty())
  39.     {
  40.         u=q.front();
  41.         q.pop();
  42.         life[u]=0;
  43.         for(int i=0;i<vec[u].size();i++)
  44.         {
  45.             if(vec[u][i].dis+dis[u]<dis[vec[u][i].to])
  46.             {
  47.                 dis[vec[u][i].to]=vec[u][i].dis+dis[u];
  48.                 if(!life[vec[u][i].to])
  49.                 {
  50.                     life[vec[u][i].to]=1;
  51.                     q.push(vec[u][i].to);
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     if(dis[t]==INF)
  57.         printf("-1\n");
  58.     else
  59.         printf("%d\n",dis[t]);
  60.     return 0;
  61. }

H 一个人的旅行 (HDU - 2066)

题意：

    中文题。

题解：

    因为点的标号范围是[1，1000]，所以可以把草儿家标为0号点，然后把所有和草儿家相邻的S个点和0号点连一条距离为0的边，然后把目的地设置为1001号点，然后把想去的D个点和1001号点连一条距离为0的边，然后求0到1001的最短路就行了。
    Dijkstra的时间复杂度为o(T*log(T))，空间复杂度为o(T)。
    spfa的时间复杂度为o(k*T)，空间复杂度为o(T)。

代码：

Dijkstra：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 2000000006
  6. struct Edge
  7. {
  8.     int to,dis;
  9.     friend bool operator <(Edge x1,Edge x2)
  10.     {
  11.         return x1.dis>x2.dis;
  12.     }
  13. }temp;
  14. int n;
  15. int dis[1005];
  16. bool life[1005];
  17. priority_queue <Edge> pq;
  18. vector <Edge> vec[1005];
  19. int main()
  20. {
  21.     int T,S,D;
  22.     int u,v;
  23.     while(~scanf("%d%d%d",&T,&S,&D))
  24.     {
  25.         for(int i=0;i<=1001;i++)
  26.         {
  27.             vec[i].clear();
  28.             life[i]=0;
  29.             dis[i]=INF;
  30.         }
  31.         while(T--)
  32.         {
  33.             scanf("%d%d%d",&u,&v,&temp.dis);
  34.             temp.to=v;
  35.             vec[u].push_back(temp);
  36.             temp.to=u;
  37.             vec[v].push_back(temp);
  38.         }
  39.         temp.dis=0;
  40.         while(S--)
  41.         {
  42.             scanf("%d",&temp.to);
  43.             vec[0].push_back(temp);
  44.         }
  45.         temp.to=1001;
  46.         while(D--)
  47.         {
  48.             scanf("%d",&u);
  49.             vec[u].push_back(temp);
  50.         }
  51.         temp.to=0;
  52.         temp.dis=0;
  53.         pq.push(temp);
  54.         while(!pq.empty())
  55.         {
  56.             temp=pq.top();
  57.             pq.pop();
  58.             if(!life[temp.to])
  59.             {
  60.                 u=temp.to;
  61.                 life[u]=1;
  62.                 dis[u]=temp.dis;
  63.                 for(int i=0;i<vec[u].size();i++)
  64.                 {
  65.                     if(!life[vec[u][i].to])
  66.                     {
  67.                         temp.to=vec[u][i].to;
  68.                         temp.dis=vec[u][i].dis+dis[u];
  69.                         pq.push(temp);
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.         if(dis[1001]==INF)
  75.             printf("-1\n");
  76.         else
  77.             printf("%d\n",dis[1001]);
  78.     }
  79.     return 0;
  80. }

spfa：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666
  6. struct Edge
  7. {
  8.     int to,dis;
  9. }temp;
  10. int n,dis[1005];
  11. bool life[1005];
  12. queue <int> q;
  13. vector <Edge> vec[1005];
  14. int main()
  15. {
  16.     int T,S,D;
  17.     int u,v;
  18.     while(~scanf("%d%d%d",&T,&S,&D))
  19.     {
  20.         for(int i=0;i<=1001;i++)
  21.         {
  22.             vec[i].clear();
  23.             life[i]=0;
  24.             dis[i]=INF;
  25.         }
  26.         while(T--)
  27.         {
  28.             scanf("%d%d%d",&u,&v,&temp.dis);
  29.             temp.to=v;
  30.             vec[u].push_back(temp);
  31.             temp.to=u;
  32.             vec[v].push_back(temp);
  33.         }
  34.         temp.dis=0;
  35.         while(S--)
  36.         {
  37.             scanf("%d",&temp.to);
  38.             vec[0].push_back(temp);
  39.         }
  40.         temp.to=1001;
  41.         while(D--)
  42.         {
  43.             scanf("%d",&u);
  44.             vec[u].push_back(temp);
  45.         }
  46.         dis[0]=0;
  47.         q.push(0);
  48.         life[0]=1;
  49.         while(!q.empty())
  50.         {
  51.             u=q.front();
  52.             q.pop();
  53.             life[u]=0;
  54.             for(int i=0;i<vec[u].size();i++)
  55.             {
  56.                 if(vec[u][i].dis+dis[u]<dis[vec[u][i].to])
  57.                 {
  58.                     dis[vec[u][i].to]=vec[u][i].dis+dis[u];
  59.                     if(!life[vec[u][i].to])
  60.                     {
  61.                         life[vec[u][i].to]=1;
  62.                         q.push(vec[u][i].to);
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.         if(dis[1001]==INF)
  68.             printf("-1\n");
  69.         else
  70.             printf("%d\n",dis[1001]);
  71.     }
  72.     return 0;
  73. }

I 六度分离 (HDU - 1869)

题意：

    中文题。

题解：

    相互认识的人之间连一条长度为1的边，任意两个人之间最多隔着6个人也就等同于任意两个人的距离不超过7。求一遍任意两个点的最短距离，然后看有没有超过7的就行了。
    多源最短路一般用Floyd算法求。
    时间复杂度o(N^3)，空间复杂度o(N^2)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. #define INF 666
  6. int dis[105][105],n,m;
  7. int main()
  8. {
  9.     int ans;
  10.     int u,v;
  11.     while(~scanf("%d%d",&n,&m))
  12.     {
  13.         ans=7;
  14.         for(int i=0;i<n;i++)
  15.         {
  16.             for(int j=0;j<n;j++)
  17.             {
  18.                 if(i==j)
  19.                     dis[i][j]=0;
  20.                 else
  21.                     dis[i][j]=INF;
  22.             }
  23.         }
  24.         while(m--)
  25.         {
  26.             scanf("%d%d",&u,&v);
  27.             dis[u][v]=dis[v][u]=1;
  28.         }
  29.         for(int k=0;k<n;k++)
  30.             for(int i=0;i<n;i++)
  31.                 for(int j=0;j<n;j++)
  32.                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
  33.         for(int i=0;i<n;i++)
  34.             for(int j=0;j<n;j++)
  35.                 ans=max(ans,dis[i][j]);
  36.         if(ans==7)
  37.             printf("Yes\n");
  38.         else
  39.             printf("No\n");
  40.     }
  41.     return 0;
  42. }

J John's trip (POJ - 1041)

题意：

    有最多m(m<=44)个点，最多n(n<=1995)条无向边，问是否存在一条路线，从第一条边所连接的序号较小点出发，经过所有的边一次，回到出发点。如果存在，输出经过的边字典序最小的一个方案。
    多组数据。

题解：

    无向图有欧拉路要满足两个条件：(1)每个点的度数都是偶数(2)任意两个有路连接的点都是连通的
    当存在欧拉路的时候，对于当前点，优先选择还没走的序号较小的边，然后先把这条边连接的另一个点作为起点继续走，然后再回头记录这条边，最后逆序输出。为什么要这样改变顺序呢？给出一组数据供思考，格式为 边序号：连接的第一个点&连接的第二个点
    1:1&2
    2:2&3
    3:1&3
    4:2&4
    5:2&4
    ps：输入比较恶心，要处理一些细节。
    时间复杂度o(n)，空间复杂度o(n)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. struct Edge
  8. {
  9.     int to,no;
  10.     friend bool operator <(Edge x1,Edge x2)
  11.     {
  12.         return x1.no>x2.no;
  13.     }
  14. }temp;
  15. vector <Edge> vec[55];
  16. int nums,l[55],cnt,ans[2005];
  17. bool life[2005],used[55];
  18. queue <int> q;
  19. void dfs(int s)
  20. {
  21.     for(;l[s]<vec[s].size();l[s]++)
  22.     {
  23.         if(life[vec[s][l[s]].no])
  24.         {
  25.             int temp=vec[s][l[s]].no;
  26.             life[vec[s][l[s]].no]=0;
  27.             dfs(vec[s][l[s]].to);
  28.             ans[cnt++]=temp;
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     bool flag;
  35.     int u,v,d,s;
  36.     while(1)
  37.     {
  38.         flag=0;
  39.         nums=0;
  40.         memset(life,0,sizeof(life));
  41.         memset(used,0,sizeof(used));
  42.         memset(l,0,sizeof(l));
  43.         for(int i=1;i<=50;i++)
  44.             vec[i].clear();
  45.         while(1)
  46.         {
  47.             scanf("%d%d",&u,&v);
  48.             if(!u && !v)
  49.                 break;
  50.             else
  51.             {
  52.                 used[u]=used[v]=1;
  53.                 if(!nums)
  54.                     s=min(u,v);
  55.                 nums++;
  56.                 scanf("%d",&temp.no);
  57.                 temp.to=u;
  58.                 vec[v].push_back(temp);
  59.                 temp.to=v;
  60.                 vec[u].push_back(temp);
  61.                 life[temp.no]=1;
  62.             }
  63.         }
  64.         if(!nums)
  65.             break;
  66.         else
  67.         {
  68.             q.push(s);
  69.             used[s]=0;
  70.             while(!q.empty())
  71.             {
  72.                 u=q.front();
  73.                 q.pop();
  74.                 for(int i=0;i<vec[u].size();i++)
  75.                 {
  76.                     if(used[vec[u][i].to])
  77.                     {
  78.                         q.push(vec[u][i].to);
  79.                         used[vec[u][i].to]=0;
  80.                     }
  81.                 }
  82.             }
  83.             for(int i=1;i<=50;i++)
  84.             {
  85.                 if(used[i] || vec[i].size()%2)
  86.                     flag=1;
  87.                 else
  88.                     sort(vec[i].begin(),vec[i].end());
  89.             }
  90.             if(flag)
  91.                 printf("Round trip does not exist.\n");
  92.             else
  93.             {
  94.                 cnt=0;
  95.                 dfs(s);
  96.                 while(nums--)
  97.                 {
  98.                     printf("%d",ans[nums]);
  99.                     if(nums)
  100.                         printf(" ");
  101.                     else
  102.                         printf("\n");
  103.                 }
  104.             }
  105.         }
  106.     }
  107.     return 0;
  108. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注