题解 P1195 【口袋的天空】

P1195 题解

其实这是一道很不错的题,有助于加深对Kruskal算法的理解,十分推荐


题目大意

先放几个定义:

  1. 子图:对于$\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$的子图。
  2. 连通块: 若$G_1$是$G$的子图,且$G_1$连通,则$G_1$是$G$的连通块。
  3. 无环连通块:若$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) //如果不够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; //如果选够n-k条边
}
cout<<ans<<endl;//输出答案
return 0;
}
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P1195-【口袋的天空】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站