MST最小生成树
分类:
IT文章
•
2023-11-29 20:33:25
首先,贴上一个很好的讲解贴:
http://www.wutianqi.com/?p=3012
HDOJ 1233 还是畅通工程
http://acm.hdu.edu.cn/showproblem.php?pid=1233
裸的Prim...
1 #include<cstdio>
2 #define MAXN 105
3 #define INF 0x3f3f3f3f
4 int map[MAXN][MAXN];
5 int dist[MAXN];
6 int vis[MAXN];
7 int n,a,b,x,ans,tot;
8 void init()
9 {
10 for(int i=1;i<=n;i++)
11 {
12 for(int j=1;j<=n;j++)
13 {
14 if(i==j) map[i][j]=0;
15 else map[i][j]=INF;
16 }
17 vis[i]=0;
18 dist[i]=INF;
19 }
20 }
21 void Prim()
22 {
23 tot=0;ans=0;
24 for(int i=1;i<=n;i++)
25 {
26 if(map[1][i]<INF)
27 dist[i]=map[1][i];
28 }
29 vis[1]=1;
30 int tmp,u=1,flag;
31 for(int i=1;i<=n;i++)
32 {
33 tmp=INF;flag=0;
34 for(int j=1;j<=n;j++)
35 {
36 if(!vis[j]&&dist[j]<tmp)
37 {
38 flag=1;
39 tmp=dist[j];
40 u=j;
41 }
42 }
43 vis[u]=1;
44 if(flag) ans+=dist[u];
45 for(int j=1;j<=n;j++)
46 {
47 if(!vis[j]&&map[u][j]<dist[j])
48 dist[j]=map[u][j];
49 }
50 }
51 }
52 int main()
53 {
54 while(scanf("%d",&n)!=EOF)
55 {
56 if(n==0) break;
57 init();
58 for(int i=0;i<n*(n-1)/2;i++)
59 {
60 scanf("%d%d%d",&a,&b,&x);
61 if(map[a][b]>x)//可能有重边,要取最小的,开始没加这个WA
62 {
63 map[a][b]=x;
64 map[b][a]=x;
65 }
66 }
67 Prim();
68 printf("%d
",ans);
69 }
70 return 0;
71 }
View Code
HDOJ 1863 畅通工程
http://acm.hdu.edu.cn/showproblem.php?pid=1863
遇见水题心情大好,哟哟切克闹,Kruskal、Prim各一套...
1 #include<cstdio>
2 #include<queue>
3 #define MAXN 105
4 using namespace std;
5 int father[MAXN];
6 int find(int x)
7 {
8 return father[x]==x?x:father[x]=find(father[x]);
9 }
10 int merge(int a,int b)
11 {
12 int fa=find(a);
13 int fb=find(b);
14 if(fa!=fb)
15 {
16 father[fa]=fb;
17 return 1;
18 }
19 return 0;
20 }
21 struct line
22 {
23 int x,y,w;
24 friend bool operator<(line a,line b)
25 {
26 return a.w>b.w;
27 }
28 };
29 line tmp;
30 priority_queue<line> q;
31 int n,m,a,b,x,ans,tot;
32 int Kruskal()
33 {
34 tot=0;
35 ans=0;
36 while(!q.empty())
37 {
38 tmp=q.top();
39 q.pop();
40 if(merge(tmp.x,tmp.y))
41 {
42 tot++;
43 ans+=tmp.w;
44 if(tot==n-1) return 1;
45 }
46 }
47 return 0;
48 }
49 void init()
50 {
51 for(int i=0;i<=n;i++)
52 {
53 father[i]=i;
54 }
55 while(!q.empty()) q.pop();
56 }
57 int main()
58 {
59 while(scanf("%d%d",&m,&n)!=EOF)
60 {
61 if(m==0) break;
62 init();
63 for(int i=0;i<m;i++)
64 {
65 scanf("%d%d%d",&a,&b,&x);
66 tmp.x=a;
67 tmp.y=b;
68 tmp.w=x;
69 q.push(tmp);
70 }
71 if(Kruskal()) printf("%d
",ans);
72 else printf("?
");
73 }
74 return 0;
75 }
View Code
1 #include<cstdio>
2 #define MAXN 105
3 #define INF 0x3f3f3f3f
4 int map[MAXN][MAXN];
5 int dist[MAXN];
6 int vis[MAXN];
7 int n,m,a,b,x,ans,tot;
8 void init()
9 {
10 for(int i=1;i<=n;i++)
11 {
12 for(int j=1;j<=n;j++)
13 {
14 if(i==j) map[i][j]=0;
15 else map[i][j]=INF;
16 }
17 dist[i]=INF;
18 }
19 }
20 int Prim()
21 {
22 ans=0;
23 for(int i=1;i<=n;i++)
24 {
25 if(map[1][i]<INF)
26 dist[i]=map[1][i];
27 vis[i]=0;
28 }
29 vis[1]=1;
30 int tmp,u=1;
31 for(int i=2;i<=n;i++)
32 {
33 tmp=INF;
34 for(int j=1;j<=n;j++)
35 {
36 if(!vis[j]&&dist[j]<tmp)
37 {
38 u=j;
39 tmp=dist[j];
40 }
41 }
42 if(vis[u]) return 0;
43 vis[u]=1;
44 ans+=tmp;
45 for(int j=1;j<=n;j++)
46 {
47 if(!vis[j]&&map[u][j]<dist[j])
48 dist[j]=map[u][j];
49 }
50 }
51 return 1;
52 }
53 int main()
54 {
55 while(scanf("%d%d",&m,&n)!=EOF)
56 {
57 if(m==0) break;
58 init();
59 for(int i=0;i<m;i++)
60 {
61 scanf("%d%d%d",&a,&b,&x);
62 if(map[a][b]>x)
63 {
64 map[a][b]=x;
65 map[b][a]=x;
66 }
67 }
68 if(Prim()) printf("%d
",ans);
69 else printf("?
");
70 }
71 return 0;
72 }
View Code
HDOJ 1875 畅通工程再续
http://acm.hdu.edu.cn/showproblem.php?pid=1875
把int换成double就行了,还有用Prim比Kruskal好点 因为每条边都得算
1 #include<cstdio>
2 #include<cmath>
3 #define INF 0x3f3f3f3f
4 #define MAXN 105
5 int point[MAXN][2];//保存点的坐标
6 double map[MAXN][MAXN];//map矩阵
7 int vis[MAXN];//访问标记数组
8 double dist[MAXN];//没有加入到MST的点到MST的最短距离
9 int n,flag;
10 double ans;
11 double calc(int x1,int y1,int x2,int y2)
12 {
13 return sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
14 }
15 int Prim()
16 {
17 ans=0;
18 for(int i=0;i<n;i++)
19 {
20 dist[i]=map[0][i];
21 vis[i]=0;
22 }
23 int u=0;
24 double temp;
25 vis[0]=1;
26 for(int i=1;i<n;i++)
27 {
28 temp=INF;
29 flag=0;
30 for(int j=0;j<n;j++)
31 {
32 if(!vis[j]&&dist[j]<temp)
33 {
34 u=j;
35 temp=dist[j];
36 flag=1;
37 }
38 }
39 if(!flag) return 0;
40 vis[u]=1;
41 ans+=dist[u];
42 for(int j=0;j<n;j++)
43 {
44 if(!vis[j]&&map[u][j]<dist[j])
45 dist[j]=map[u][j];
46 }
47 }
48 return 1;
49 }
50 void create()
51 {
52 double tmp;
53 for(int i=0;i<n;i++)
54 {
55 for(int j=i+1;j<n;j++)
56 {
57 tmp=calc(point[i][0],point[i][1],point[j][0],point[j][1]);
58 if(tmp<10.0||tmp>1000.0)
59 {
60 map[i][j]=INF;
61 map[j][i]=INF;
62 }else
63 {
64 map[i][j]=tmp;
65 map[j][i]=tmp;
66 }
67 }
68 map[i][i]=0.0;
69 }
70 }
71 int main()
72 {
73 int T;
74 scanf("%d",&T);
75 while(T--)
76 {
77 scanf("%d",&n);
78 for(int i=0;i<n;i++)
79 {
80 scanf("%d%d",&point[i][0],&point[i][1]);
81 }
82 create();
83 if(Prim()) printf("%.1f
", ans*100);
84 else puts("oh!");
85 }
86 }
View Code
HDOJ 1879 继续畅通工程
http://acm.hdu.edu.cn/showproblem.php?pid=1879
对于已经建好的路 只需在建图时把边权赋为0 然后用Prim或者Kruskal求一棵MST即可
1 #include<cstdio>
2 #define MAXN 105
3 #define INF 0x3f3f3f3f
4 int map[MAXN][MAXN];
5 int dist[MAXN];
6 int vis[MAXN];
7 int n,m,a,b,x,ans,tot,op;
8 void init()
9 {
10 for(int i=1;i<=n;i++)
11 {
12 for(int j=1;j<=n;j++)
13 {
14 if(i==j) map[i][j]=0;
15 else map[i][j]=INF;
16 }
17 dist[i]=INF;
18 }
19 }
20 int Prim()
21 {
22 ans=0;
23 for(int i=1;i<=n;i++)
24 {
25 if(map[1][i]<INF)
26 dist[i]=map[1][i];
27 vis[i]=0;
28 }
29 vis[1]=1;
30 int tmp,u=1;
31 for(int i=2;i<=n;i++)
32 {
33 tmp=INF;
34 for(int j=1;j<=n;j++)
35 {
36 if(!vis[j]&&dist[j]<tmp)
37 {
38 u=j;
39 tmp=dist[j];
40 }
41 }
42 if(vis[u]) return 0;
43 vis[u]=1;
44 ans+=tmp;
45 for(int j=1;j<=n;j++)
46 {
47 if(!vis[j]&&map[u][j]<dist[j])
48 dist[j]=map[u][j];
49 }
50 }
51 return 1;
52 }
53 int main()
54 {
55 while(scanf("%d",&n)!=EOF)
56 {
57 if(n==0) break;
58 init();
59 for(int i=0;i<n*(n-1)/2;i++)
60 {
61 scanf("%d%d%d%d",&a,&b,&x,&op);
62 if(op==1) x=0;//已经建好的路 权值赋为0 然后求一棵MST即可
63 if(map[a][b]>x)
64 {
65 map[a][b]=x;
66 map[b][a]=x;
67 }
68 }
69 if(Prim()) printf("%d
",ans);
70 else printf("?
");
71 }
72 return 0;
73 }
View Code
ZOJ 3204 Connect them
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3367
这题要求按最小的字典序输出最小生成树中的边的各个顶点...
在用Kruskal的时候,在边入优先队列的时候就得按照权值,x坐标,y坐标排序,
否则取得的最小生成树可能就是不符合题意的,这样在输出时候按照字典序输出了也是WA
1 #include<cstdio>
2 #include<queue>
3 #include<algorithm>
4 #define INf 0x3f3f3f3f
5 #define MAXN 105
6 using namespace std;
7 // int map[MAXN][MAXN];
8 int father[MAXN];
9 int n,tot,a;
10 int find(int x)
11 {
12 return father[x]==x?x:father[x]=find(father[x]);
13 }
14 int merge(int a,int b)
15 {
16 int fa=find(a);
17 int fb=find(b);
18 if(fa!=fb)
19 {
20 father[fa]=fb;
21 return 1;
22 }
23 return 0;
24 }
25 struct line
26 {
27 int x,y,w;
28 friend bool operator<(line a,line b)//在找边时候同样权值的边也得按照字典序来取 开始没写后两行判断 WA数次...
29 {
30 if(a.w!=b.w)return a.w>b.w;
31 else if(a.x!=b.x)return a.x>b.x;
32 else return a.y>b.y;
33 }
34 };
35 line print[5050];
36 line tmp;
37 priority_queue<line> q;
38 void Kruskal()
39 {
40 tot=0;
41 while(!q.empty())
42 {
43 tmp=q.top();
44 q.pop();
45 if(merge(tmp.x,tmp.y))
46 {
47 print[tot++]=tmp;
48 }
49 }
50 }
51 void init()
52 {
53 for(int i=1;i<=n;i++)
54 {
55 father[i]=i;
56 }
57 while(!q.empty()) q.pop();
58 }
59 bool cmp(line a,line b)
60 {
61 if(a.x==b.x) return a.y<b.y;
62 else return a.x<b.x;
63 }
64 int main()
65 {
66 int T;
67 scanf("%d",&T);
68 while(T--)
69 {
70 scanf("%d",&n);
71 init();
72 for(int i=1;i<=n;i++)
73 {
74 for(int j=1;j<=n;j++)
75 {
76 scanf("%d",&a);
77 if(a!=0&&i<j)
78 {
79 tmp.x=i;
80 tmp.y=j;
81 tmp.w=a;
82 q.push(tmp);
83 }
84 }
85 }
86 Kruskal();
87 if(tot==n-1)
88 {
89 sort(print,print+n-1,cmp);
90 for(int i=0;i<n-2;i++)
91 {
92 printf("%d %d ", print[i].x,print[i].y);
93 }
94 printf("%d %d
", print[n-2].x,print[n-2].y);
95 }else
96 {
97 printf("-1
");
98 }
99 }
100 }
View Code
POJ 2349 Arctic Network
http://poj.org/problem?id=2349
这题有点难度,关键是分析出问题的本质...
要求任意两个不用卫星连通的城市之间的距离不超过d,则d越小,这个图被分成的连通块数量越多,卫星的数量就是连通块的数量-1
所以要求的d是一个恰好使这个图分成k+1个连通分量的一个最小值...
然后有这么一个定理:一个值能把这个图分成k个连通分量,则肯定能把这个图的最小生成树分成k个连通分量...
亦即 求最小生成树中的第K长边,可以想到Kruskal用的就是每次加入一条最小边的贪心法形成一棵MST
最小生成树共有n-1条边,第k长边,也就是Kruskal加入的第(n-k)条边,问题得解...具体见代码
1 #include<cstdio>
2 #include<queue>
3 #include<cmath>
4 #define MAXN 550
5 // #define INF 0x3f3f3f3f
6 using namespace std;
7 int k,n,cnt;
8 int father[MAXN];
9 int find(int x)
10 {
11 return father[x]==x?x:father[x]=find(father[x]);
12 }
13 int merge(int a,int b)
14 {
15 int fa=find(a);
16 int fb=find(b);
17 if(fa!=fb)
18 {
19 father[fa]=fb;
20 return 1;
21 }
22 return 0;
23 }
24 struct edge
25 {
26 int x,y;
27 double w;
28 friend bool operator<(edge a,edge b)
29 {
30 return a.w>b.w;
31 }
32 };
33 edge tmp;
34 priority_queue<edge> q;
35 int point[MAXN][2];
36 double clac(int x1,int y1,int x2,int y2)
37 {
38 return sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
39 }
40 void add()
41 {
42 for(int i=0;i<n;i++)
43 {
44 for(int j=i+1;j<n;j++)
45 {
46 tmp.x=i;
47 tmp.y=j;
48 tmp.w=clac(point[i][0],point[i][1],point[j][0],point[j][1]);
49 q.push(tmp);
50 }
51 }
52 }
53 double Kruskal()
54 {
55 for(int i=0;i<n;i++)
56 father[i]=i;
57 cnt=0;
58 while(!q.empty())
59 {
60 tmp=q.top();
61 q.pop();
62 if(merge(tmp.x,tmp.y))
63 {
64 cnt++;
65 if(cnt==n-k) return tmp.w;//做了一点优化,找到第k长边就返回,快了大概200ms
66 }
67 }
68 return 0;
69 }
70 int main()
71 {
72 int T;
73 scanf("%d",&T);
74 while(T--)
75 {
76 while(!q.empty()) q.pop();
77 scanf("%d%d",&k,&n);
78 for(int i=0;i<n;i++)
79 {
80 scanf("%d%d",&point[i][0],&point[i][1]);
81 }
82 add();
83 printf("%.2f
",Kruskal());
84 }
85 return 0;
86 }
View Code
持续更新中...