codeforces Dima and Bacteria

题意：给出n，m和k，表示有n个细菌，m种仪器和k种细菌，给出k种细菌的数量ci，然后每个细菌按照种类排成一排（所以有第i种细菌的序号从∑（1≤j≤i-1）cj + 1 到∑（1≤j≤i）cj）；接下来给出m种仪器，有u，v，x三个值，表示说从可以在第u，v号细菌之间移动能量，代价为x。请帮助判断说这些细菌是否正确，正确的前提条件是说同种细菌之间移动能量为0，如果正确的话，给出两两细菌（种类）间移动能量的最小值。

思路：并差集+floyd；

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 100010
  5 using namespace std;
  6 const int inf=1<<29;
  7 
  8 int n,m,k;
  9 int g[600][600];
 10 int c[maxn];
 11 int f[maxn],u[maxn],v[maxn],x[maxn];
 12 int num[maxn];
 13 int xx[maxn];
 14 int sum[maxn];
 15 
 16 int Find(int x)
 17 {
 18     if(x==f[x]) return x;
 19     return f[x]=Find(f[x]);
 20 }
 21 
 22 
 23 int main()
 24 {
 25      while(scanf("%d%d%d",&n,&m,&k)!=EOF)
 26      {
 27          int fx,fy;
 28         for(int i=1; i<=k; i++)
 29         {
 30             scanf("%d",&c[i]);
 31             sum[i]=sum[i-1]+c[i];
 32         }
 33         for(int i=1; i<=n; i++)
 34         {
 35             f[i]=i;
 36         }
 37         for(int i=1; i<=k; i++)
 38         {
 39             for(int j=sum[i-1]+1; j<=sum[i]; j++)
 40             {
 41                 xx[j]=i;
 42             }
 43         }
 44         for(int i=1; i<=m; i++)
 45         {
 46             scanf("%d%d%d",&u[i],&v[i],&x[i]);
 47             int uu=u[i],vv=v[i];
 48             if(uu>vv) swap(uu,vv);
 49             fx=Find(uu);
 50             fy=Find(vv);
 51             if(x[i]==0)
 52             {
 53                 if(fx!=fy)
 54                 {
 55                     f[fy]=fx;
 56                 }
 57             }
 58         }
 59         bool flag=false;
 60         for(int i=1; i<=k; i++)
 61         {
 62             int x=Find(sum[i-1]+1);
 63             int cnt=0;
 64             for(int j=sum[i-1]+1; j<=sum[i]; j++)
 65             {
 66                 if(Find(j)==x) cnt++;
 67             }
 68             if(cnt!=c[i])
 69             {
 70                 flag=true;
 71                 break;
 72             }
 73         }
 74         if(flag)
 75         {
 76             printf("No
");
 77         }
 78         else
 79         {
 80             for(int i=1; i<=k; i++)
 81             {
 82                 for(int j=1; j<=k; j++)
 83                 {
 84                     if(i==j) g[i][j]=0;
 85                     else g[i][j]=inf;
 86                 }
 87             }
 88             for(int i=1; i<=m; i++)
 89             {
 90                 g[xx[u[i]]][xx[v[i]]]=min(g[xx[u[i]]][xx[v[i]]],x[i]);
 91                 g[xx[v[i]]][xx[u[i]]]=min(g[xx[v[i]]][xx[u[i]]],x[i]);
 92             }
 93             for(int c=1; c<=k; c++)
 94             {
 95                 for(int i=1; i<=k; i++)
 96                 {
 97                     if(i==c)continue;
 98                     for(int j=1; j<=k; j++)
 99                     {
100                        if(i==j||j==c) continue;
101                        g[i][j]=min(g[i][j],g[i][c]+g[c][j]);
102                     }
103                 }
104             }
105             printf("Yes
");
106             for(int i=1; i<=k; i++)
107             {
108                 for(int j=1; j<=k; j++)
109                 {
110                     if(g[i][j]==inf&&i!=j)
111                     {
112                         printf("-1 ");
113                     }
114                     else printf("%d ",g[i][j]);
115                 }
116                 printf("
");
117             }
118         }
119      }
120      return 0;
121 }

View Code