WHU 1542 Countries (floyd)

题意：

　　在小明出生的星球X上有n国家。

　　一些国家通过结盟而拥有良好的双边关系，因此他们的公民得益于这些政策，使得所有这些国家之间的旅行变得免费。

　　但是，不同联盟之间的旅行就不是这么容易了。如果可能，它必须花一些钱。

　　请帮小明计算出国家之间的最小花费。

　　输入：

　　　　输入包含多组样例。

　　　　每组样例的第一行有两个整数 n 和 m 。(1<=n<=10^5, 1<=m<=10^5)

　　　　接下来的m行，每行有x, y, c。其中 c 表示 x, y之间的花费。如果c为0，则表示x和y属于同一个联盟。(1<=x, y<=n, 0<=c<=10^9)

　　　　你可以假设两个国家之间没有多于一条路。

　　　　然后下一行是一个整数q，代表有多少个询问。(1<=q<=200)

　　　　接下来有q行，每行包括x, y。(1<=x, y<=n)

　　　　保证不会超过两百个联盟。

　　　　当输入n=0时，结束。

　　输出：

　　　　对于每组输入，每个询问输出一行。如果不可能，输出"-1"。

思路：

　　对于同一个联盟的国家，我们可以把他们看成一个国家，因为他们一定是连起来的。然后跑floyd。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const int MAXN = (int) 1e5+7;
11 const int MAXC = 205;
12 
13 struct Edge{
14     int x, y;
15     ll c;
16 }a[MAXN];
17 
18 int p[MAXN];
19 int f[MAXN];
20 ll d[MAXC][MAXC];
21 int n, m, q;
22 int cnt;
23 
24 int Find(int x) {
25     int res = x;
26     int t;
27 
28     while (f[res]!=res) res = f[res];
29     while (x!=res) {
30         t = x;
31         x = f[x];
32         f[t] = res;
33     }
34     return res;
35 }
36 
37 void Union(int x, int y) {
38     f[Find(x)] = Find(y);
39 }
40 
41 void floyd() {
42     for (int k = 0; k < cnt; k++)
43         for (int i = 0; i < cnt; i++)
44             for (int j = 0; j < cnt; j++)
45                 if (-1!=d[i][k] && -1!=d[k][j]) {
46                     if (-1==d[i][j]) {
47                         d[i][j] = d[i][k]+d[k][j];
48                     } else
49                         d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
50                 }
51 }
52 
53 int main() {
54     #ifdef Phantom01
55         freopen("WHU1542.txt", "r", stdin);
56     #endif // Phantom01
57 
58     while (scanf("%d", &n)!=EOF) {
59         if (0==n) break;
60         scanf("%d", &m);
61         cnt = 0;
62         for (int i = 1; i <= n; i++)
63             f[i] = i;
64         for (int i = 0; i < m; i++) {
65             scanf("%d%d%lld", &a[i].x, &a[i].y, &a[i].c);
66             if (0 == a[i].c) Union(a[i].x, a[i].y);
67         }
68         for (int i = 1; i <= n; i++) {
69             if (i==f[i]) //如果是根，
70                 p[i] = cnt++;
71         }
72         for (int i = 0; i < cnt; i++) {
73             for (int j = 0; j < cnt; j++)
74                 d[i][j] = -1;
75             d[i][i] = 0;
76         }
77         int x, y;
78         for (int i = 0; i < m; i++) {
79             x = p[Find(a[i].x)];
80             y = p[Find(a[i].y)];
81             d[x][y] = -1==d[x][y] ? a[i].c : min(d[x][y], a[i].c);
82             d[y][x] = -1==d[y][x] ? a[i].c : min(d[y][x], a[i].c);
83         }
84         floyd();
85         scanf("%d", &q);
86         for (int i = 0; i < q; i++) {
87             scanf("%d%d", &x, &y);
88             printf("%lld
", d[p[Find(x)]][p[Find(y)]]);
89         }
90     }
91 
92     return 0;
93 }

View Code