专题六 最小生成树 | 李博的博客
0%

专题六 最小生成树

POJ 1251 Jungle Roads

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
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
const int MAXN=27+10;//最大点数
const int MAXM=75+10;//最大边数
int F[MAXN];//并查集使用
struct Edge{
int u,v,w;
}edge[MAXM];
int tol;//边数,加边前赋值为0
void addedge(int u,int v,int w){
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
//排序函数,将边按照权值从小到大排序
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int find(int x){
if(F[x]==-1) return x;
else return F[x]=find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回-1
int Kruskal(int n){
memset(F,-1,sizeof F);
sort(edge,edge+tol,cmp);
int cnt=0;//计算加入的边数
int ans=0;
for(int i=0;i<tol;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2){
ans+=w;
F[t1]=t2;
cnt++;
}
if(cnt==n-1) break;
}
if(cnt<n-1) return -1;//不连通
else return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int n,k,w;
char u,v;
while(cin>>n&&n){
tol=0;//初始化边数
for(int i=1;i<n;i++){
cin>>u>>k;
while(k--){
cin>>v>>w;
addedge(u-'A',v-'A',w);
}
}
cout<<Kruskal(n)<<"\n";
}
}

POJ 1287 Networking

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
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
const int MAXN=50+10;
const int MAXM=MAXN*MAXN;
struct Edge{
int u,v,w;
}edge[MAXM];
int tol=0;
int F[MAXN];
void addedge(int u,int v,int w){
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int find(int x){
if(F[x]==-1) return x;
else return F[x]=find(F[x]);
}
int Kruskal(int n){
memset(F,-1,sizeof F);
sort(edge,edge+tol,cmp);
int ans=0,cnt=0;
for(int i=0;i<tol;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2){
ans+=w;
cnt++;
F[t1]=t2;
}
if(cnt==n-1) break;
}
if(cnt<n-1) return -1;
else return ans;
}
int main(){
int n,m,u,v,w;
while(cin>>n&&n){
cin>>m;
int sum=0;
tol=0;
while(m--){
cin>>u>>v>>w;
addedge(u,v,w);
}
cout<<Kruskal(n)<<"\n";
}
return 0;
}

POJ 2031 Building a Space Station

POJ 2421 Constructing Roads

ZOJ 1586 QS Network

POJ 1789 Truck History

POJ 2349 Arctic Network

POJ 1751 Highways

POJ 1258 Agri-Net

POJ 3026 Borg Maze

分析: 就是在一个迷宫中从 $S$ 出发去抓所有外星人👽 $A$ ,问你最短路径,因为可以在 $S$ 和 $A$ 处分裂,所以相当于计算路径覆盖的边的最少个数。

显然这就转换成了最小生成树问题。先从 $N+1$ 个点分别作为起点进行 $BFS$ ,记录到其它点的最短路径,这就生成了一个无向完全图,既然是个稠密图那就跑一个 $Prim$ 算法求最小生成树,然后这棵树的边长和就是答案。

时间复杂度 $O(TN^2)$

注意:测试数据特别坑,输入的迷宫尺寸后面会有很多空格,好像也有一些空行,参考我的输入即可。

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
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <complex>
using namespace std;
#define LL long long
const int maxside = 50 + 10;
char maze[maxside][maxside], id[maxside][maxside];
int T, N, C, R; // C->column R->row
struct Point{
int x, y, step;
Point(){}
Point(int _x, int _y, int _step){
this->x = _x;
this->y = _y;
this->step = _step;
}
inline bool isLegal(){
return x > 0 && x <= R && y > 0 && y <= C && maze[x][y] != '#';
}
};
struct Queue{
Point node[maxside * maxside];
int fr, re;// front rear
inline void clear(){
fr = re = 0;
}
inline bool empty(){
return (fr == re);
}
inline void push(const Point &x){
node[re++] = x;
}
inline Point front_pop(){
return node[fr++];
}
}qu;
bool vis[maxside][maxside];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dis[maxside * maxside][maxside * maxside];
inline void BFS(int sx, int sy){
memset(vis, false, sizeof vis);
qu.clear();
int step = 0;
qu.push(Point(sx, sy, step));
vis[sx][sy] = 1;
while(!qu.empty()){
Point cur = qu.front_pop();

for(int i = 0; i < 4; ++i){
Point nex(cur.x + dir[i][0], cur.y + dir[i][1], cur.step + 1);
if(!nex.isLegal() || vis[nex.x][nex.y]) continue;
if(maze[nex.x][nex.y] == 'S' || maze[nex.x][nex.y] == 'A') {
dis[id[sx][sy]][id[nex.x][nex.y]] = nex.step;
}
qu.push(nex);
vis[nex.x][nex.y] = 1;
}
}
}

const int INF = 0x3f3f3f3f;
bool inMST[maxside * maxside];
int lowc[maxside * maxside];
int Prim(){
int ans = 0;
memset(inMST, false, sizeof inMST);
inMST[0] = true;
for(int i = 1; i < N; i++){
lowc[i] = dis[0][i];
}
for(int i = 1; i < N; i++){
int minc = INF;
int p = -1;
for(int j = 0; j < N; j++){
if(!inMST[j] && minc > lowc[j]){
minc = lowc[j];
p = j;
}
}
if(minc == INF) return -1;//原图不联通
ans += minc;
inMST[p] = true;
for(int j = 0; j < N; j++){
if(!inMST[j] && lowc[j] > dis[p][j]){
lowc[j] = dis[p][j];
}
}
}
return ans;
}
int main () {
scanf("%d", &T);
while (T--){
scanf("%d%d", &C, &R);
//Read for an extra time to skip the empty line.
for (int i = 0; i <= R; ++i){
gets(maze[i]+1);
}
N = 1;
for(int i = 1; i <= R; ++i){
for(int j = 1; j <= C; ++j){
if(maze[i][j] == 'S') id[i][j] = 0;
else if(maze[i][j] == 'A') id[i][j] = N++;
}
}
memset(dis, 0, sizeof dis);
for(int i = 1; i <= R; ++i){
for(int j = 1; j <= C; ++j){
if(maze[i][j] == 'S' || maze[i][j] == 'A') BFS(i, j);
}
}
printf("%d\n", Prim());
}
}

POJ 1679 The Unique MST

HDU 1233 还是畅通工程

HDU 1301 Jungle Roads

HDU 1875 畅通工程再续

如果对您有帮助,请我喝杯奶茶?