ReZero's Utopia.

通畅工程问题

Word count: 858Reading time: 4 min
2016/10/22 Share

在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。

input

  • 有多组输入数据。每组第一行输入三个整数n、m、c(1<=n,m,c<=100000),分别代表城市数量,可建道路数量和单位长度道路修建费用。接下来m行每行三个整数u、v(1<=u,v<=n)、d(1<=d<=100000)。代表可建道路的起点城市、终点城市和长度。

output

  • 每组数据输出一行,输出数据组数和使所有城市连通的最小费用,无法全部连通输出-1。

Kruskal算法的步骤:

1.对所有边进行从小到大的排序。 2.每次选一条边(最小的边),如果如果形成环,就不加入(u,v)中,否则加入。那么加入的(u,v)一定是最佳的。

并查集解决,略微优化:路径压缩

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>

using namespace std;

///Kruskal算法的步骤:
///1.对所有边进行从小到大的排序。
///2.每次选一条边(最小的边),如果如果形成环,就不加入(u,v)中,否则加入。
///那么加入的(u,v)一定是最佳的。

///构成环的条件就是u,v已经连通,则不能添加
///关于这一点可用并查集查掌门解决

typedef struct Node{
int beg;
int las;
int len;
}Node;

Node node[10200];
int prev[10200] = {0};

bool cmp(Node a, Node b){
return a.len < b.len;
}

int finds(int x){
int r = x;
while(prev[r] != r){
r = prev[r];
}
return r;
}

bool join(int x, int y){
int fx = finds(x), fy = finds(y);
if(fx != fy){
prev[fx] = fy;///fx != fy,即无共同顶点,不构成三点环
return 1;
}
return 0;
}

int main(){
int cases; cin >> cases;
for(int kase = 1; kase <= cases; ++kase){
int n, m, c, sum = 0, tree = 0;
cin >> n >> m >> c;
for(int i = 1; i <= n; ++i){
prev[i] = i;
}
for(int i = 0; i < m; ++i){
int u, v, d;
cin >> node[i].beg >> node[i].las >> node[i].len;
}
sort(node, node + m, cmp);
for(int i = 0; i < m; ++i){
if(join(node[i].beg, node[i].las)){
sum += node[i].len;
}
}
for(int i = 1; i <= n; ++i){
if(prev[i] == i){
tree++;
}
}
cout << "Case #" << kase << ":" << " ";
if(tree > 1){
cout << "-1";
}
else {
cout << sum*c;
}
cout << endl;
}

}

> 傻逼的爆了一堆超时,二次弱逼式优化



#include <bits/stdc++.h>

using namespace std;

struct Node{
int beg;
int las;
int len;
}node[100100];

int prevs[100100];

int cmp(const Node &a, const Node &b){
return a.len < b.len;
}

int finds(int x){
int r = x;
while(prevs[r] != r){
r = prevs[r];
}
int t = x;
while(t != r){
int tf = prevs[t];
prevs[t] = r;
t = tf;
}
return r;
}

bool join(int x, int y){
int fx = finds(x), fy = finds(y);
if(fx != fy){
prevs[fx] = fy;
return 1;
}
return 0;
}

int main(){
int cases; scanf("%d", &cases);
for(int kase = 1; kase <= cases; ++kase){
int n, m, c, sides = 0;
long long sum = 0;
scanf("%d%d%d", &n, &m, &c);
for(int i = 1; i <= n; ++i){
prevs[i] = i;
}
for(int i = 0; i < m; ++i){
scanf("%d%d%d", &node[i].beg, &node[i].las, &node[i].len);
}
sort(node, node + m, cmp);
for(int i = 0; i < m; ++i){
if(join(node[i].beg, node[i].las)){
sum += node[i].len;
sides++;
if(sides == n-1) break;
}
}
printf("Case #%d: ", kase);

if(sides == n-1) {
printf("%lld",sum*c);
}else {
printf("-1");
}
printf("\n");
}
return 0;
}
CATALOG
  1. 1. 在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。
    1. 1.1. input
    2. 1.2. output
      1. 1.2.1. Kruskal算法的步骤:
      2. 1.2.2. 并查集解决,略微优化:路径压缩