题意：给你一个无向有权的图，图上的点被分成了几类，对于同类的点你需要判断它们之间相互的最短距离是不是0.满足这个条件之后要输出的是类与类之间的最短距离的矩阵。点给到10^5这么多，判断同类的点显然不能跑最短路，所以直接的方法必然是并查集，对边为0的点做一次并查集，对同类的点判一下find(x)==find(y)就可以了。 然后就是将同类的点抽象出一个新的点，这个时候只有500个点，然后就可以跑一下floyd了。 题意有坑的地方，所以没有AC比赛的时候。 这题倒是很好的练了一下基础的内容并查集和floyd。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#include<queue>#define ll long long#define maxn 100500#define inf 0x3f3f3f3fusing
namespace std;vector<int> ZG[maxn];int
type[550];int
sum[550];int
n, m, k;int
fa[maxn];int
find(int
x){ return
fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}bool
deterMine(int
index){ int
sid = sum[index - 1]; for
(int i = sid + 1; i <= sid + type[index]; i++){ if
(find(sid + 1) != find(i)) return
false; } return
true;}int
dist[550][550];int
main(){ while
(cin >> n >> m >> k) { sum[0] = 0; for
(int i = 1; i <= k; i++){ scanf("%d", &type[i]); sum[i] = sum[i - 1] + type[i]; } int
ui, vi, wi; memset(dist, 0x3f, sizeof(dist)); for
(int i = 0; i <= n; i++) fa[i] = i; for
(int i = 0; i <= k; i++) { dist[i][i] = 0; } for
(int i = 0; i < m; i++){ scanf("%d%d%d", &ui, &vi, &wi); int
ut = lower_bound(sum, sum + 1 + k, ui) - sum; int
vt = lower_bound(sum, sum + 1 + k, vi) - sum; dist[ut][vt] = min(dist[ut][vt], wi); dist[vt][ut] = min(dist[vt][ut], wi); if
(wi == 0) { if
(find(ui) != find(vi)){ fa[find(ui)] = fa[find(vi)]; } } } for
(int i = 1; i <= n; i++) find(i); bool
flag = true; for
(int i = 1; i <= k; i++){ if
(deterMine(i) == false){ flag = false; } } if
(!flag) { puts("No"); continue; } puts("Yes"); for
(int kk = 1; kk <= k; kk++){ for
(int i = 1; i <= k; i++){ for
(int j = 1; j <= k; j++){ if
(dist[i][kk] + dist[kk][j] < dist[i][j]){ dist[i][j] = dist[i][kk] + dist[kk][j]; } } } } for
(int i = 1; i <= k; i++){ for
(int j = 1; j <= k; j++){ if
(j != 1) printf(" "); if
(dist[i][j] < inf) printf("%d", dist[i][j]); else
printf("%d", -1); } puts(""); } } return
0;} |
Codeforces400D Dima and Bacteria,布布扣,bubuko.com
Codeforces400D Dima and Bacteria
原文：http://www.cnblogs.com/chanme/p/3583728.html