P1195 题解
其实这是一道很不错的题,有助于加深对Kruskal算法的理解,十分推荐
题目大意
先放几个定义:
- 子图:对于$\forall G_1=(V_{G_1},E_{G_1})$,有$V_{G_1}\in V_G \land E_{G_1}\in E_G$,则$G_1$是$G$的子图。
- 连通块: 若$G_1$是$G$的子图,且$G_1$连通,则$G_1$是$G$的连通块。
- 无环连通块:若$G_1$是$G$的连通块,且$G_1$中不含有环,则则$G_1$是$G$的无环连通块。
题目大意:求使用边集中的边,将$n$个孤立的点连成$k$个连通块所需的最小边权和。
思路
首先,如果想要边权和最小,所有的连通块都应该是无环连通块。原理很简单:如果连通块中有环的话,则一定可以删去一条边使边权和变小。因此,我们很容易想到用Kruskal算法解决。
性质:
由Kruskal算法的步骤我们可以得出以下性质:
在一个图中保留$n-k$条边,则图中至多有$k$个无环连通块。
证明:
首先,当k=1时,命题显然成立(此时图中唯一的无环连通块是图的生成树)
接下来,设k=a时命题成立(即连通块有a个),则k=a+1时,因为边数减少了一条,则原图中一定有一个无环连通块失去了一条边。又因为无环连通块的无环性,无环连通块中的每一条边都是桥。因此这条边的失去一定会使原无环连通块分裂为两个更小的无环连通块,因此总的连通块个数增加1,变为a+1,命题成立。
因此,由数学归纳法可得,原命题成立。
证毕。
接下来,解题的思路便已经很明朗了:直接使用Kruskal算法,将选$n-1$条边后停止变为$n-k$条边后停止。
代码:
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<algorithm> #include<cstring> using namespace std; struct edge{ int f=0,t=0,w=0; edge(int a,int b,int c) : f(a),t(b),w(c) {} edge() {} }; struct cmp{ bool operator () (edge a,edge b) { return a.w<b.w; } }; edge e[10005]; int f[1005]; int n,m,k; int Count=0,ans=0; void init() { for(int i=1;i<=n;i++) f[i]=i; } int getf(int v) { if(f[v]==v) return f[v]; f[v]=getf(f[v]); return f[v]; } bool merge(int a,int b) { int x=getf(a); int y=getf(b); if(x!=y) { f[x]=y; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>k; for(int i=1;i<=m;i++) { cin>>e[i].f>>e[i].t>>e[i].w; } sort(e+1,e+m+1,cmp()); init(); if(m<n-k) { cout<<"No Answer"<<endl; return 0; } for(int i=1;i<=m;i++) { if(merge(e[i].f,e[i].t)) { ++Count; ans+=e[i].w; } if(Count==n-k) break; } cout<<ans<<endl; return 0; }
|