武大预选赛F题-（裸并查集+下标离散化+floyd最短路）

116 阅读 0 评论 77 点赞

我是靠谱客的博主如意金鱼，这篇文章主要介绍武大预选赛F题-（裸并查集+下标离散化+floyd最短路），现在分享给大家，希望可以做个参考。

Problem 1542 - F - Countries
Time Limit: 1000MS Memory Limit: 65536KB
Total Submit: 266 Accepted: 36 Special Judge: No
Description
There are n countries at planet X on which Xiao Ming was born.

Some countries, which have been sharing fine bilateral relations, form a coalition and thus all of their citizens will benefit from a policy for which all the travels between these countries will become totally free.

But it is not easy to travel between countries distributed in different coalitions. If possible, it must cost some money called YZB(yu zhou bi) which is always positive.

Help Xiao Ming determine the minimum cost between countries.
Input
The input consists of one or more test cases.

First line of each test case consists two integers n and m. (1<=n<=10^5, 1<=m<=10^5)

Each of the following m lines contains: x y c, and c indicating the YZB traveling from x to y or from y to x. If it equals to zero, that means x and y are in the same coalition. (1<=x, y<=n, 0<=c<=10^9)
You can assume that there are no more than one road between two countries.

Then the next line contains an integer q, the number of queries.(1<=q<=200)

Each of the following q lines contains: x y. (1<=x, y<=n)

It is guaranteed that there are no more 200 coalitions.

Input is terminated by a value of zero (0) for n.
Output
For each test case, output each query in a line. If it is impossible, output “-1”.

Sample Input
6 5
1 2 0
2 4 1
3 5 0
1 4 1
1 6 2
3
4 2
1 3
4 6
0
Sample Output
1
-1

AC代码如下：

复制代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF1 1000000000000000001
#define INF2 1000000009
const int maxn = 100010;
struct node{
int s,e,w;
}map[maxn];
long long d[201][201];
long long fa[maxn];
int n, m;
int h[maxn];
void init(int a)
{
for(int i = 0; i <= a; i++)
{
fa[i] = i;
h[i] = 0;
}
for(int i = 0; i <= a; i++){
map[i].w = INF2;
}
}
int Find(int x)
{
if(fa[x] == x)
return x;
else
return fa[x] = Find(fa[x]);
}
void unite(int x,int y)
{
x = Find(fa[x]);
y = Find(fa[y]);
if(x == y) return;
else
{
if(h[x] > h[y]) fa[y] = fa[x];
else
{
fa[x] = fa[y];
if(h[x] == h[y]) h[y]++;
}
}
}
bool M[maxn];
int s[maxn];
int r;
void discretize(){
memset(M, false, sizeof(M));
//memset(s, 0, sizeof(s));
int k;
for(int i = 1; i <= n; i++){
k = Find(i);
if(!M[k]){
s[k] = r++;
M[k] = true;
}
}
for(int i = 1; i < r; i++){
for(int j = 1; j < r; j++){
if(i == j) d[i][j] = 0;
else d[i][j] = INF1;
}
}
for(int j = 1; j <= m; j++){
if(map[j].w != 0){
int dx = Find(map[j].s);
int dy = Find(map[j].e);
dx = s[dx];
dy = s[dy];
d[dx][dy] = d[dy][dx] = min(d[dx][dy],(long long)map[j].w);
//cout<<"*"<<d[dx][dy]<<"*"<<endl;
}
}
}
void floyd(int r){
for(int k = 1; k < r; k++)
for(int i = 1; i < r; i++)
for(int j = 1; j < r; j++){
if(d[i][k] < INF1 && d[k][j] < INF1) d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
}
}
void input(int m){
for(int i = 1; i <= m; i++){
int a , b;
scanf("%d%d",&map[i].s, &map[i].e);
scanf("%d",&map[i].w);
if(map[i].w == 0) unite(map[i].s, map[i].e);
}
}
int main(){
while(cin>>n>>m&&n){
init(n);
input(m);
r = 1;
discretize();
floyd(r);
int q;
cin>>q;
while(q--){
int a, b;
scanf("%d%d",&a, &b);
a = Find(a);
b = Find(b);
a = s[a];
b = s[b];
if(d[a][b] == INF1) printf("-1n");
else
printf("%lldn",d[a][b]);
}
}
}

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF1 1000000000000000001
#define INF2 1000000009
const int maxn = 100010;
struct node{
int s,e,w;
}map[maxn];
long long d[201][201];
long long fa[maxn];
int n, m;
int h[maxn];
void init(int a)
{
for(int i = 0; i <= a; i++)
{
fa[i] = i;
h[i] = 0;
}
for(int i = 0; i <= a; i++){
map[i].w = INF2;
}
}
int Find(int x)
{
if(fa[x] == x)
return x;
else
return fa[x] = Find(fa[x]);
}
void unite(int x,int y)
{
x = Find(fa[x]);
y = Find(fa[y]);
if(x == y) return;
else
{
if(h[x] > h[y]) fa[y] = fa[x];
else
{
fa[x] = fa[y];
if(h[x] == h[y]) h[y]++;
}
}
}
bool M[maxn];
int s[maxn];
int r;
void discretize(){
memset(M, false, sizeof(M));
//memset(s, 0, sizeof(s));
int k;
for(int i = 1; i <= n; i++){
k = Find(i);
if(!M[k]){
s[k] = r++;
M[k] = true;
}
}
for(int i = 1; i < r; i++){
for(int j = 1; j < r; j++){
if(i == j) d[i][j] = 0;
else d[i][j] = INF1;
}
}
for(int j = 1; j <= m; j++){
if(map[j].w != 0){
int dx = Find(map[j].s);
int dy = Find(map[j].e);
dx = s[dx];
dy = s[dy];
d[dx][dy] = d[dy][dx] = min(d[dx][dy],(long long)map[j].w);
//cout<<"*"<<d[dx][dy]<<"*"<<endl;
}
}
}
void floyd(int r){
for(int k = 1; k < r; k++)
for(int i = 1; i < r; i++)
for(int j = 1; j < r; j++){
if(d[i][k] < INF1 && d[k][j] < INF1) d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
}
}
void input(int m){
for(int i = 1; i <= m; i++){
int a , b;
scanf("%d%d",&map[i].s, &map[i].e);
scanf("%d",&map[i].w);
if(map[i].w == 0) unite(map[i].s, map[i].e);
}
}
int main(){
while(cin>>n>>m&&n){
init(n);
input(m);
r = 1;
discretize();
floyd(r);
int q;
cin>>q;
while(q--){
int a, b;
scanf("%d%d",&a, &b);
a = Find(a);
b = Find(b);
a = s[a];
b = s[b];
if(d[a][b] == INF1) printf("-1n");
else
printf("%lldn",d[a][b]);
}
}
}