codeforces 400D Dima and Bacteria 并查集+floyd

题目链接：http://codeforces.com/problemset/problem/400/D

题目大意：

　　给定n个集合，m步操作，k个种类的细菌，

　　第二行给出k个数表示连续的xi个数属于i集合。

　　当某个种类之间两两交换的值都为0可行解，则输出所有种类之间交换的最小值；否则输出No

解题思路：当两点之间的距离为0时并查集到一个集合中，只需保证最终同一种类的细菌都在一个并查集中则是符合条件的可行解，再用FLOYD找最短路即可

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 #define FFF 100005
  8 int set[FFF];
  9 int a[FFF];
 10 int sw[505][505];
 11 int cnt[505];
 12 int vis[FFF];
 13 int n,k,m;
 14 
 15 int find(int x)
 16 {
 17     if(x==set[x])
 18         return x;
 19     else return set[x]=find(set[x]);
 20 }
 21 
 22 void uion(int x,int y)
 23 {
 24     int l1=find(x);
 25     int l2=find(y);
 26     if(l1==l2)
 27         return;
 28     else
 29         set[l2]=l1;
 30     return;
 31 }
 32 
 33 bool judge()
 34 {
 35     for(int l=1;l<=k;l++)
 36     {
 37         int tmp=-1;
 38         for(int i=cnt[l-1]+1;i<=cnt[l];i++)
 39         {
 40             if(tmp==-1)
 41                 tmp=find(i);
 42             else
 43             {
 44                 if(tmp!=find(i))
 45                     return false;
 46             }
 47         }
 48     }
 49     return true;
 50 }
 51 
 52 void solve()
 53 {
 54     for(int l=1;l<=k;l++)
 55     {
 56         for(int i=1;i<=k;i++)
 57         {
 58             if(i!=l)
 59             {
 60                 for(int j=1;j<=k;j++)
 61                 {
 62                     if(j!=l&&j!=i)
 63                     {
 64                         if((sw[i][l]+sw[l][j]<sw[i][j]||sw[i][j]<0)&&sw[i][l]>=0&&sw[l][j]>=0)
 65                             sw[i][j]=sw[i][l]+sw[l][j];
 66                     }
 67                 }
 68             }
 69         }
 70     }
 71     return;
 72 }
 73 
 74 void print()
 75 {
 76     for(int i=1;i<=k;i++)
 77     {
 78         sw[i][i]=0;
 79         for(int j=1;j<=k;j++)
 80         {
 81             if(j==1)
 82                 printf("%d",sw[i][j]);
 83             else
 84                 printf(" %d",sw[i][j]);
 85         }
 86         cout<<endl;
 87     }
 88     return;
 89 }
 90 
 91 int main()
 92 {
 93     int i,j,now;
 94     scanf("%d%d%d",&n,&m,&k);
 95     //n为点的总个数，m为边数，k为种类数
 96     for(i=1,now=1;i<=k;i++)
 97     {
 98         int x;
 99         scanf("%d",&x);
100         // 第i种细菌有x个
101         for( j=0;j<x;j++)
102         {
103             a[j+now]=i;
104             set[j+now]=j+now;
105         }
106         now+=x;
107         cnt[i]=now-1;
108     }
109     memset(sw,-1,sizeof(sw));
110     // 两两种类之间的代价初始化成-1
111     while(m--)
112     {
113         int x,y,z;
114         scanf("%d%d%d",&x,&y,&z);
115         if(a[x]==a[y])
116         //属于同一种类
117         {
118             if(z==0)
119                 uion(x,y);
120             // 添入并查集
121         }
122         else
123         //不同种类的细菌
124         {
125             if(z==0)
126                 uion(x,y);
127             if(sw[a[x]][a[y]]==-1)
128             // 该两类之间还没有交换代价
129                 sw[a[x]][a[y]]=sw[a[y]][a[x]]=z;
130             else if(z<sw[a[x]][a[y]])
131             // 新的代价较小的情况
132                 sw[a[x]][a[y]]=sw[a[y]][a[x]]=z;
133         }
134     }
135     if(!judge())
136     // 判断同种类的细菌之间是否为0
137         printf("No
");
138     else
139     {
140         printf("Yes
");
141         solve();
142         // floyd找最短路
143         print();
144     }
145     return 0;
146 }
147 
148 /*
149 FLOYD
150 题目大意：给定n个集合，m步操作，k个种类的细菌，
151             第二行给出k个数表示连续的xi个数属于i集合。
152             当某个种类之间两两交换的值都为0可行解
153 解题思路：当两点之间的距离为0时并查集到一个集合中，
154             最终保证同种细菌都在一个并查集中
155             再用FLOYD找最短路*/

View Code