[关闭]
@Asuna 2017-02-21T11:45:00.000000Z 字数 4696 阅读 971

2016寒假集训队第九次作业

题解

Problem A:最短路

题意：寻找最短的从商店到赛场的路线。

题解：最短路模版题。mark一下模版。
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int d[110],w[110][110],vis[110],n,m,a,b,c;
  7. void dijkstra(int s)
  8. {
  9.     for (int i=1; i<=n; i++)
  10.         d[i]=10000000;
  11.     d[s] = 0;
  12.     memset(vis, 0, sizeof(vis));
  13.     for (int i=1; i<=n; i++)
  14.     {
  15.         int u=-1;
  16.         for (int j=1; j<=n; j++)
  17.             if (!vis[j])
  18.             {
  19.                 if (u==-1 || d[j]<d[u]) u=j;
  20.             }
  21.         vis[u]=1;
  22.         for (int j=1; j<=n; j++)
  23.             if (!vis[j])
  24.             {
  25.                 int tmp=d[u]+w[u][j];
  26.                 if (tmp<d[j]) d[j]=tmp;
  27.             }
  28.     }
  29. }
  31. int main()
  32. {
  33.     while(cin>>n>>m)
  34.     {
  35.         if (n==0 && m==0) break;
  36.         for (int i=1; i<=n; i++)
  37.         {
  38.             w[i][i]=10000000;
  39.             for (int j=i+1; j<=n; j++)
  40.                 w[i][j]=w[j][i]=100000000;
  41.         }
  42.         for (int i=0; i<m; i++)
  43.         {
  44.             cin>>a>>b>>c;
  45.             w[a][b]=w[b][a]=c;
  46.         }
  47.         dijkstra(1);
  48.         cout<<d[n]<<endl;
  49.     }
  50.     return 0;
  51. }

Problem B: Wormholes

题意：已知从一个农场到另一个农场的一些通道和所需的时间，一些虫洞（虫洞是单向通道，可以回到前一段时间），问这个人能否回到起始地方。

题解：构造出图，将农田抽象成点，通道抽象成边，这样可以将虫洞抽象成负边，判断是否存在负环，这样就可以用Bellman_Ford求解。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<stack>
  5. #include<algorithm>
  6. using namespace std;
  7. struct node
  8. {
  9.     int u,v,w;
  10. }que[10010];
  11. int t,n,m,wh,cnt,inf=999999999,dis[5010],t1,t2,t3;
  13. bool bellman_ford()
  14. {
  15.     memset(dis,inf,sizeof(dis));
  16.     dis[1]=0;
  17.     int flag,a,b,c;
  18.     for (int i=1; i<n; i++)
  19.     {
  20.         flag=0;
  21.         for (int j=0; j<cnt; j++)
  22.         {
  23.             a=que[j].u;
  24.             b=que[j].v;
  25.             c=que[j].w;
  26.             if (dis[b]>dis[a]+c)
  27.             {
  28.                 dis[b]=dis[a]+c;
  29.                 flag=1;
  30.             }
  31.         }
  32.         if(!flag)
  33.             break;
  34.     }
  35.     for (int j=0; j<cnt; j++)
  36.     {
  37.         a=que[j].u;
  38.         b=que[j].v;
  39.         c=que[j].w;
  40.         if(dis[b]>dis[a]+c)
  41.             return true;
  42.     }
  43.     return false;
  44. }
  46. int main()
  47. {
  48.     cin>>t;
  49.     while (t--)
  50.     {
  51.         cnt=0;
  52.         cin>>n>>m>>wh;
  53.         for(int i=1; i<=m; i++)
  54.         {
  55.             cin>>t1>>t2>>t3;
  56.             que[cnt].u=t1;
  57.             que[cnt].v=t2;
  58.             que[cnt].w=t3;
  59.             cnt++;
  60.             que[cnt].u=t2;
  61.             que[cnt].v=t1;
  62.             que[cnt].w=t3;
  63.             cnt++;
  64.         }
  65.         for (int i=m+1; i<=m+wh; i++)
  66.         {
  67.             cin>>t1>>t2>>t3;
  68.             que[cnt].u=t1;
  69.             que[cnt].v=t2;
  70.             que[cnt].w=-t3;
  71.             cnt++;
  72.         }
  73.         if (bellman_ford()) cout<<"YES"<<endl;
  74.         else cout<<"NO"<<endl;
  75.     }
  76.     return 0;
  77. }

Problem C:tockbroker Grapevine

题意：每个人传递消息同时进行，求最后一个人知道消息的最短时间。

题解：先枚举每个人为起点的情况，然后这个情况下求每个人知道消息的最短时间，然后遍历一遍找到最大的那个，就是最后一个人收到消息的时间了。然后比较出所以情况中最后一个人知道消息的时间的最小值。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. #include<cmath>
  7. using namespace std;
  8. int n,dis[10010],a[1010][1010],book[10010],minn,v,m,x,y,maxx,k;
  9. void dijstra(int s)
  10. {
  11.     for (int i=1; i<=n; i++) dis[i]=99999999;
  12.     dis[s]=0;
  13.     for (int i=1; i<=n; i++)
  14.         book[i]=0;
  15.     for (int i=1; i<=n; i++)
  16.     {
  17.         int minn=99999999;
  18.         for (int j=1; j<=n; j++)
  19.         {
  20.             if (dis[j]<minn && book[j]==0)
  21.             {
  22.                 minn=dis[j];
  23.                 v=j;
  24.             }
  25.         }
  26.         book[v]=1;
  27.         for (int j=1; j<=n; j++)
  28.         {
  29.             if (book[j]==0)
  30.             {
  31.                 if (dis[j]>dis[v]+a[v][j])
  32.                 {
  33.                     dis[j]=dis[v]+a[v][j];
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     return;
  39. }
  41. int main()
  42. {
  43.     while(cin>>n)
  44.     {
  45.         if (n==0) break;
  46.         for (int i=1; i<=n; i++)
  47.         {
  48.             for (int j=1; j<=n; j++)
  49.             {
  50.                 if (i<=j)
  51.                     a[i][j]=a[j][i]=99999999;
  52.             }
  53.         }
  54.         for (int i=1; i<=n; i++)
  55.         {
  56.             cin>>m;
  57.             for(int j=1; j<=m; j++)
  58.             {
  59.                 cin>>x>>y;
  60.                 a[i][x]=y;
  61.             }
  62.         }
  63.         minn=99999999;
  64.         k=0;
  65.         for (int i=1; i<=n; i++)
  66.         {
  67.             dijstra(i);
  68.             maxx=0;
  69.             for (int j=1; j<=n; j++)
  70.             {
  71.                 if (j!=i)
  72.                 {
  73.                     if (dis[j]>maxx) maxx=dis[j];
  74.                 }
  75.             }
  76.             //cout<<maxx<<" "<<minn<<endl;
  77.             if (maxx<minn)
  78.             {
  79.                 minn=maxx;
  80.                 k=i;
  81.             }
  82.         }
  83.         if (k!=0) cout<<k<<" "<<minn<<endl;
  84.         else cout<<"disjoint"<<endl;
  85.     }
  86.     return 0;  
  87. }

Problem D:昂贵的聘礼

题意：娶到酋长女儿的最小代价，即到达终点的最短距离。

题解：枚举的最小等级，枚举过程中把小于这个等级，差距大于m的删去。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. using namespace std;
  6. int w[110][110],n,m,x,k,minn,l[110],p[110],dis[110],vis[110],within[110],boss,cost,ans;
  8. int dijkstra ()
  9. {
  10.     int k,minn;
  11.     memset(vis,0,sizeof(vis));
  12.     for (int i=1; i<=n; i++)
  13.         dis[i]=w[1][i];
  14.     dis[1]=0;
  15.     vis[1]=1;
  16.     for (int i=1; i<=n; i++)
  17.     {
  18.         minn=999999999;
  19.         for (int j=1; j<=n; j++)
  20.         {
  21.             if (!vis[j] && within[j] && dis[j]<minn)
  22.             {
  23.                 k=j;
  24.                 minn=dis[j];
  25.             }
  26.         }
  27.         if (minn==999999999)
  28.             break;
  29.         vis[k]=1;
  30.         dis[k]=minn;
  31.         for (int j=1; j<=n; j++)
  32.             if (!vis[j] && within[j] && dis[k]+w[k][j]<dis[j])
  33.                 dis[j]=dis[k]+w[k][j];
  34.     }
  35.     minn=999999999;
  36.     for (int i=1; i<=n; i++)
  37.         if (dis[i]+p[i]<minn && vis[i])
  38.             minn=dis[i]+p[i];
  39.     return minn;
  40. }
  42. int main()
  43. {
  44.     cin>>m>>n;
  45.     for (int i=1; i<=n; i++)
  46.         for (int j=1; j<=n; j++)
  47.             if (i==j) w[i][j]=0;
  48.             else w[i][j]=999999999;
  49.     for (int i=1; i<=n; i++)
  50.     {
  51.         cin>>p[i]>>l[i]>>x;
  52.         for (int j=0; j<x; j++)
  53.         {
  54.             cin>>k;
  55.             cin>>w[i][k];
  56.         }
  57.     }
  58.     boss=l[1];
  59.     ans=999999999;
  60.     for (int i=0; i<=m; i++)
  61.     {
  62.         memset(within,0,sizeof(within));
  63.         for (int j=1; j<=n; j++)
  64.         {
  65.             if (boss-l[j]<=m-i && l[j]-boss<=i)
  66.                 within[j]=1;
  67.         }
  68.         cost=dijkstra();
  69.         if (cost<ans) ans=cost;
  70.     }
  71.     cout<<ans<<endl;
  72.     return 0;
  73. }

Problem F:Choose the best route

题意：给定一个有向图，多个起点，一个终点，求起点到终点的最短路。

题解：将0看成出发点，将n个能选择的点看做事0的相邻并且花费为0的点，那么就是求0到S的最小花费了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int n,m,s,x,y,t,w[1005][1005],vis[1005],dis[1005];
  8. void dijkstra()
  9. {
  10.     int minn,k;
  11.     memset(vis,0,sizeof(vis));
  12.     vis[0]=1;
  13.     for (int i=0; i<=n; i++)
  14.         dis[i]=w[0][i];
  15.     for (int i=0; i<=n; i++)
  16.     {
  17.         minn=100000000;
  18.         for (int j=0; j<=n; j++)
  19.         {
  20.             if (dis[j]<minn && !vis[j])
  21.             {
  22.                 k=j;
  23.                 minn=dis[j];
  24.             }
  25.         }
  26.         vis[k]=1;
  27.         for (int j=0; j<=n; j++)
  28.         {
  29.             if (dis[k]+w[k][j]<dis[j] && !vis[j])
  30.                 dis[j]=dis[k]+w[k][j];
  31.         }
  32.     }
  33. }
  36. int main()
  37. {
  38.     while(cin>>n>>m>>s)
  39.     {
  40.         for (int i=0; i<=n; i++)
  41.             for (int j=0; j<=n; j++)
  42.                 w[i][j]=100000000;
  43.         for (int i=1; i<=m; i++)
  44.         {
  45.             scanf("%d%d%d",&x,&y,&t);
  46.             if (t<w[x][y])
  47.                 w[x][y]=t;
  48.         }
  49.         cin>>m;
  50.         for (int i=1; i<=m; i++)
  51.         {
  52.             scanf("%d",&x);
  53.             w[0][x]=0;
  54.         }
  55.         dijkstra();
  56.         if (dis[s]==100000000) cout<<-1<<endl;
  57.         else cout<<dis[s]<<endl;
  58.     }
  59.     return 0;
  60. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注