最小生成树
最小生成树
一个有 n 个结点的连通图的生成树包含原图中的所有 n 个结点，并且有保持图连通的最少的边,且边的权值之和最小。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
实现方式
prim
适用于邻接矩阵
const int oo=100000000; //表示无穷
prim(){
//任意选一点作为初始集合，一般选点1作为初始集合
for(int i=2; i<=n; i++){
//计算其他点到集合的距离(也就是到点1的距离)，并标记未计算
cost[i]=dis[1][i]; used[i]=0;
}
for(int r=2; r<=n; r++){
int len=oo, x;
for(int i=2; i<=n; i++) if(used[i]==0){
//在未计算的点中寻找离集合最近的点记录为x，最近距离为len
if(cost[i]<len){
len=cost[i]; x=i;
}
}
ans+=len; //最小生成树答案累加len
used[x]=1; //将x点合并到集合，x点标记已计算
for(int i=2; i<=n; i++) if(used[i]==0){
//使用x点去更新未计算点到集合距离
cost[i]=min(cost[i], dis[i][x]);
}
}
} 复杂度: O(n^2)
kruskal
基于并查集,适用于点较多,边较少的情况 以下代码的作用: 生成最小生成树,输出最大边
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[305];
struct node{
int u,v,w;
}p[100005];
bool cmp(node x,node y){ //按边权从小到大排序
return x.w<y.w;
}
int find(int x){ //并查集寻找父亲
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++){
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
}
sort(p+1,p+m+1,cmp); //边权排序
for(int i=1; i<=n; i++) fa[i]=i; //并查集初始化
int k=0;
for(int i=1; i<=m; i++){
int a=p[i].u, b=p[i].v, c=p[i].w;
a=find(a), b=find(b);
if(a!=b){ //两个结点不在同个集合，合并
k++;
fa[b]=a;
if(k==n-1){ //合并n-1次，最小生成树完成
//最后一次合并的边权为最大边权
printf("%d %d\n",n-1,c);
break;
}
}
}
return 0;
}复杂度: O(e log e) (e表示边的数量)
kruskal逆运用
题目描述
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。 PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。
输入
输入的第一行是一个整数n，表示生成树的节点数。 接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。 （顶点的边号在1-n之间，边权<maxint）
输出
一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。
样例输入 #1
3
1 2 4
2 3 7样例输出 #1
19样例输入 #2
4
1 2 1
1 3 1
1 4 2样例输出 #2
12数据范围： n<20000
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,f[20010],d[20010];
ll ans;
struct node{
int a,b,c;
}e[20010];
bool cmp(node xx,node yy){
return xx.c<yy.c;
}
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
int main(){
scanf("%d",&n);
for(int i=1; i<n; i++){
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
ans+=e[i].c; //累加部分和
}
sort(e+1,e+n,cmp); //先排序(kruskal必备)
for(int i=1; i<=n; i++) f[i]=i,d[i]=1; //初始化
for(int i=1; i<n; i++){
int u=find(e[i].a),v=find(e[i].b);
f[v]=u; //合并
ans+=((ll)d[u]*d[v]-1)*(e[i].c+1); //累加剩下的和
//u,v所在的集合的其他点相互之间长度至少e[i].c+1,边数总共为d[u]*d[v]-1
d[u]+=d[v]; //合并
}
printf("%lld",ans);
return 0;
} 常规例题
题目描述
图中共有N个点的完全图，每条边都有权值，每个点也有权值。要求选出M个点和M-1条边，构成一棵树，使得： 所有边的权值比所有点的权值之和的比率最小。 给定N和M，以及N个点的权值，和所有的边权，要求M个点的最小比率生成树。
输入
第一行包含两个整数N和M(2<=N<=15，2<=M<=N)，表示点数和生成树的点数。 接下来一行N个整数，表示N个点的边权。 最后N行，每行N列，表示完全图中的边权。所有点权和边权都在[1,100]之间。
输出
输出最小比率生成树的M个点。当答案出现多种时，要求输出的第一个点的编号尽量小，第一个相同，则第二个点的编号尽量小，依次类推，中间用空格分开。编号从1开始。
样例输入
3 2
30 20 10
0 6 2
6 0 3
2 3 0样例输出
1 3代码(状压)
#include<bits/stdc++.h>
using namespace std;
int g[25][25];
int n,m,anse,ansn,ans,a[25],b[25],mark[25],dist[25];
int judge(int t,int s){ //比较状态t和状态s谁的字典序最小
for(int i=1; i<=m; i++){
int j=1<<(i-1);
if((t&j)==0&&(s&j)==1) return 1;
if((t&j)==1&&(s&j)==0) return 0;
}
return 0; //返回0表示t小，反之s小
}
void solve(int s){
int nw=0,ew=0;
for(int i=1; i<=m; i++) nw+=a[b[i]],mark[i]=0;
for(int i=2; i<=m; i++) dist[i]=g[b[1]][b[i]];
for(int i=2; i<=m; i++){
int minlen=1e8, v=0;
for(int j=2; j<=m; j++){
if(mark[j]==0 && dist[j]<minlen){
minlen=dist[j]; v=j;
}
}
ew=ew+minlen;
mark[v]=1;
for(int j=2; j<=m; j++){
if(mark[j]==0 && dist[j]>g[b[j]][b[v]])
dist[j]=g[b[j]][b[v]];
}
}
if(ans==0 || ew*ansn<nw*anse || (ew*ansn==nw*anse && judge(ans,s))){
ansn=nw; anse=ew; ans=s;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) scanf("%d",&g[i][j]);
int sta=(1<<n)-1;
for(int s=1; s<=sta; s++){
int c=0;
for(int i=1; i<=n; i++){ //判断状态中有几个点
int j=1<<(i-1);
if(s&j){
c++;
b[c]=i; //进行tag标记,方便prim中调用第i个点
}
}
if(c==m) solve(s);
}
for(int i=1; i<=n; i++){
int j=1<<(i-1);
if(ans&j) printf("%d ",i); //输出状态中的点
}
return 0;
} 变形运用
题目描述
Famer John希望把水源引入他的N (1 <= N <= 300) 个牧场，牧场的编号是1～N。他将水源引入某个牧场的方法有两个，一个是在牧场中打一口井，另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连。在牧场i中打井的费用是W_i (1 <= W_i <= 100000)。把牧场i和j用一根管道相连的费用是P_ij (1 <= P_ij <= 100000, P_ij = P_ji, P_ii = 0)。请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源。
输入
第1行: 一个正整数N. 第2～N+1行: 第i+1行包含一个正整数W_i. 第N+2～2N+1行: 第N+1+i行包含N个用空格分隔的正整数,第j个数表示P_ij.
输出
最少要花多少钱才能够让他的所有牧场都有水源。
样例输入
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0样例输出
9提示
输入数据解释 总共有四个牧场.在1号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要3的费用.在不同的牧场间建立管道需要2,3或4的费用. 输出数据解释 Farmer John需要在4号牧场打一口井,然后把所有牧场都用管道连到1号牧场上,总共的花费是3+2+2+2=9. 对于30%的数据N<=10 对于60%的数据N<=100 对于100%的数据N<=300
思路
每个点打井代价理解为当前点到集合的初始距离，然后每次选择最短距离的点合并，总共合并n次。
代码
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[305],used[305],g[305][305];
void prim(){
for(int i=1; i<=n; i++){ //总共寻找n个点
int x,len=1e8;
for(int j=1; j<=n; j++) if(used[j]==0){
if(a[j]<len){
len=a[j];
x=j;
}
} //每次寻找代价最小的点
ans+=len;
used[x]=1;
for(int j=1; j<=n; j++)
if(used[j]==0){
a[j]=min(a[j],g[x][j]);
//新的代价可以理解为本身打井的代价和连边代价的较小值
}
}
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++) scanf("%d",&g[i][j]);
}
prim();
printf("%d\n",ans);
return 0;
}
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/8/
