图论之最小生成树问题(kruskal)
最近有几位同学催我更新,于是来摸摸鱼,来讲一下最小生成树问题。
所谓最小生成树(MST),就是在一张无向带权图中的一棵经过所有节点,边权和最小的一棵树。在实际生活中,可以运用于城镇之间的修路上。
对于MST问题,通常有两种算法,prim算法以及kruskal算法,其中最常用的算法为kruskal算法,其与并查集结合之后可以以O(ElogE)的时间复杂度解决问题,对于稀疏图而言,是一种非常优秀的算法,但是,对于稠密图而言,更适合使用prim算法。这次就只介绍一下kruskal算法。
kruskal算法本质是一种贪心算法,我们知道,树一定无环,我们先对所有边以边权从小到大进行排序,然后从小到大逐个选边,将端点存入并查集中,若边的两个端点发现在同一个并查集中,则会成环,就跳过这个边,否则就把这条边存入MST中。这样我们就得到了一棵最小生成树。易证这种算法的正确性。至于并查集的介绍可以参见我之前的博客。
例题1 hdu1233
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 83393 Accepted Submission(s): 37809
当N为0时,输入结束,该用例不被处理。
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=(1e5)+5;
const int maxm=(1e5)+5;
vector<int>g[maxn];
int par[maxn];
int depth[maxn];
int n,m;
//并查集
void init(int n){
for(int i=0;i<=n;i++){
par[i]=i;
depth[i]=0;
}
}
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void unit(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
if(depth[x]<depth[y])par[x]=y;
else{
par[y]=x;
if(depth[x]==depth[y])depth[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
//kruskal算法
struct Edge{
int u,v,w;
}edge[maxm];
bool cmp(Edge x,Edge y){
return x.w<y.w;
}
int kruskal(){
int ans=0;
init(n);
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=m;i++){
int a=find(edge[i].u);
int b=find(edge[i].v);
if(a==b)continue;//成环
unit(a,b);
ans+=edge[i].w;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
while(n){
m=n*(n-1)/2;
for(int i=1;i<=m;i++){
cin>>edge[i].u>>edge[i].v>>edge[i].w;
}
cout<<kruskal()<<endl;
cin>>n;
}
return 0;
}
例题2 poj2421
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 35679 | Accepted: 16044 |
Description
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
题目大意:已知有某些边已经建立了,问使这张图联通的代价是多少。
解析:依然是最小生成树问题,只是先预存边到并查集中,再跑kruskal即可。
代码如下
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=105;
const int maxm=10005;
int par[maxn];
int depth[maxn];
int n,m;
void init(int n){
for(int i=0;i<=n;i++){
par[i]=i;
depth[i]=0;
}
}
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void unit(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
if(depth[x]<depth[y])par[x]=y;
else{
par[y]=x;
if(depth[x]==depth[y])depth[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
struct Edge{
int u,v,w;
}edge[maxm];
bool cmp(Edge x,Edge y){
return x.w<y.w;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
edge[++cnt].u=i;
edge[cnt].v=j;
edge[cnt].w=x;
}
}
m=cnt;
init(n);
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(!same(x,y))unit(x,y);
}
sort(edge+1,edge+m+1,cmp);
int ans=0;
for(int i=1;i<=m;i++){
int a=find(edge[i].u);
int b=find(edge[i].v);
if(a==b)continue;
unit(a,b);
ans+=edge[i].w;
}
cout<<ans<<endl;
return 0;
}
例题3:poj2377
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 21954 | Accepted: 8892 |
Description
Realizing Farmer John will not pay her, Bessie decides to do the worst job possible. She must decide on a set of connections to install so that (i) the total cost of these connections is as large as possible, (ii) all the barns are connected together (so that it is possible to reach any barn from any other barn via a path of installed connections), and (iii) so that there are no cycles among the connections (which Farmer John would easily be able to detect). Conditions (ii) and (iii) ensure that the final set of connections will look like a "tree".
Input
* Lines 2..M+1: Each line contains three space-separated integers A, B, and C that describe a connection route between barns A and B of cost C.
Output
Sample Input
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
Sample Output
42
Hint
The most expensive tree has cost 17 + 8 + 10 + 7 = 42. It uses the following connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=(1e3)+5;
const int maxm=(2e4)+5;
vector<int>g[maxn];
int n,m;
int par[maxn];
int depth[maxn];
void init(int n){
for(int i=0;i<=n;i++){
par[i]=i;
depth[i]=0;
}
}
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void unit(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
if(depth[x]<depth[y])par[x]=y;
else{
par[y]=x;
if(depth[x]==depth[y])depth[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
struct Edge{
int u,v,w;
}edge[maxm];
bool cmp(Edge x,Edge y){
return x.w>y.w;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>edge[i].u>>edge[i].v>>edge[i].w;
}
sort(edge+1,edge+m+1,cmp);
init(n);
ll ans=0;
for(int i=1;i<=m;i++){
int a=find(edge[i].u);
int b=find(edge[i].v);
if(a==b)continue;
unit(a,b);
ans+=edge[i].w;
}
int x=find(1);
for(int i=1;i<=n;i++){
if(find(i)!=x){
ans=-1;
break;
}
}
cout<<ans<<endl;
return 0;
}
总结:kruskal代码看似较长,实际上思路就是简单的贪心以及与并查集的结合,多数可以用模板直接套,修改以下细节即可。
摸结束,谢谢阅读。
最新文章
- android.util.TypedValue.applyDimension
- Android应用内语言切换实现(转)
- angular.js初探
- shell脚本ssh自动登陆服务器
- oracle建立表空间
- iOS开发 - 不进入待机(屏幕保持唤醒)---UIApplication学习
- 【从零开始】用node搭建一个jsonp&;json服务
- C++多态?
- Web缓存(一) - HTTP协议缓存
- 最近公共祖先(LCT)
- STP(Spanning Tree Protocol)
- Nginx http反向代理流程Proxy_pass模块
- top 分析
- Springboot2.x 集成jsp
- jxl和POI的区别
- css3实现文本渐变
- 入门智能家居,从 IFTTT 到 HomeKit 自动化(二)
- ci 3.0 默认路由放在子文件夹 无法访问的解决办法
- 盒子模型之margin相关技巧!
- mybatis模糊查询防止SQL注入