最小生成树的相关算法
学完最小生成树就来学习下它的相关算法吧。。。
在最小生成树的实际应用中我们常常会遇到这一类问题，给你一张无向带权连通图和两个节点u,v让你求u,v之间的一条路径使得u->v路径上最大的边权最小值。这一类问题我们称之为最小瓶颈路问题。
最小瓶颈路
对于最小瓶颈路，要分两种情况讨论，一种是单次询问，一种是多次询问。
1、单次询问
首先，我们从最简单的一个询问来说。我们很容易就能想到对于这一类问题我们可以先求出最小生成树然后在树上执行一次dfs然后就能求出答案了，我想这种应该是最简单的做发复杂度是O(mlogm)能够满足题目的需求。复杂度是不能优化了，但我们可不可以减少一下代码的长度呢，在这里我引用郭华阳在2007年发表的国家集训队论文里的算法。
郭华阳在国家集训队论文里介绍的最小生成树的性质，就是在kruskal算法执行的时候第一次将两个点（或者说两个点的集合）连起来的那条边就是这两点的最小瓶颈路上最大边。（因为kruskal是从小到大依次连边的。）
例题
poj2253 forgger（经典老题）
#include<iostream>
using namespace std;
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 205
struct Edge{
int u,v;
double w;
}edge[N*N];
int n,t;
struct D{
double x,y;
}dian[N];
int father[N];
void add_edge(int a,int b)
{
++t;
edge[t].u=a;
edge[t].v=b;
edge[t].w=sqrt((dian[a].x-dian[b].x)*(dian[a].x-dian[b].x)+(dian[a].y-dian[b].y)*(dian[a].y-dian[b].y));
}
bool cmp(Edge P,Edge Q)
{
return P.w<Q.w;
}
int find(int x)
{
return (father[x]==x?x:father[x]=find(father[x]));
}
void kruskal(double &ans)
{
for(int i=1;i<=n;++i)
father[i]=i;
sort(edge+1,edge+t+1,cmp);
for(int l=1;l<=t;++l)
{
int f1=find(edge[l].u);
int f2=find(edge[l].v);
if(f1==f2) continue;
father[f2]=f1;
if(find(1)==find(2)) /*1是起点，2是终点，在kruskal算法执行的时候第一次将两个点（或者说两个点的集合）连起来的那条边就是这两点的最小瓶颈路上最大边。*/
{
ans=edge[l].w;/*这个性质由kruskal算法的过程即可知道*/
return;
}
}
}
int main()
{
int topt=0;
while(scanf("%d",&n)==1)
{
topt++;
if(n==0) break;
t=0;
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&dian[i].x,&dian[i].y);
if(i==1)continue;
for(int j=1;j<i;++j)
add_edge(j,i);
}
double ans;
kruskal(ans);
printf("Scenario #%d\n",topt);
printf("Frog Distance = %0.3lf\n\n",ans);
}
return 0;
}
还有例题luoguP2330
给出题解（用的一种麻烦的方法做的）
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 10000
using namespace std;
struct node
{
int x,y,v;
}g[MAX];
int father[MAX];
void make(int n)
{
for (int i=1;i<=n;i++)
father[i]=i;
}
int find(int x)
{
if (father[x]!=x) father[x]=find(father[x]);
return father[x];
}
void unionn(int x,int y)
{
x=find(x);
y=find(y);
father[y]=x;
}
bool judge(int x,int y)
{
x=find(x);
y=find(y);
if (x==y) return 1;
else return 0;
}
bool cmp(node x,node y)
{
return x.v<y.v;
}
main()
{
int n,c;
scanf("%d%d",&n,&c);
printf("%d ",n-1);
for (int i=1;i<=c;i++)
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].v);
make(c);
int k=0;
int tot=0;
sort(g+1,g+c+1,cmp);
for (int i=1;i<=c;i++)
{
if (find(g[i].x) != find(g[i].y))
{
unionn(g[i].x,g[i].y);
tot=max(g[i].v,tot);
k++;
}
if (k==n-1) break;
}
printf("%d",tot);
}
还有一种很简单的floyed。。。。
把floyd算法中的‘之和’，’取最小值’改成’最大值’和’取最小值’即可。。。
#include<iostream>
#include<algorithm>
#define INF 100000000
using namespace std;
int g[310][310];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) g[i][j]=INF;
else g[i][j]=0;
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
cin>>g[u][v];
g[v][u]=g[u][v];
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=k&&k!=j&&i!=j)
if(g[i][j]>max(g[i][k],g[k][j]))
g[i][j]=max(g[i][k],g[k][j]);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]>ans) ans=g[i][j];
cout<<n-1<<" "<<ans<<endl;
return 0;
}
2、多次查询
单个询问非常的简单但是对于多组询问上述解法就没有用武之地了。那这时候我们怎么处理呢？利用lca处理，下面列出算法步骤：
因为要多次访问，所以的话先预处理。因为最短路一定是在最小生成树里的，所以，先求最小生成树，然后把最小生成树改成有根树，有根树中引入层的概念，根据到根节点的距离，分层，如果两个点在同一层，就可以从两边同时找向上层遍历来，因为从两边遍历，所以更省时间，因为层数相同，所以任意两点在向上层遍历的时候必会有祖先相同（此时两点之间就找到了一条路了，而且此路必然就是所求的路了）的情况，此时就找左边点到相同祖先的路的最大边，以及右边的点到相同祖先节点的路的最大边，然后取最大值。。。
例题
uva 11354（只找到这样一道）
#include<stdio.h>
#include<string.h>
#include<queue>
#define MEM(x,y) memset(x,y,sizeof(x))
#define max(x,y) x<y?y:x
#define INF 51000
#define Max 1000000000
using namespace std;
struct edge //整个图中的边
{
friend bool operator <(edge x,edge y)
{
return x.len > y.len;
}
int x,y,len;
};
struct MSTedge //最小生成树中的边
{
int x,len,next;
}MSTe[2*INF];
int n,m,q;
int cnt;
int parent[INF],head[INF]; //head[]存以该点为起点的边在边集中的下标
priority_queue<edge>Q; //存储整个图的边
//将MST变成有根树时使用的变量
int father[INF],dis[INF]; //fatehr[]用来记录该节点在有根树中的父节点，dis[]用来记录该点的层数
int cost[INF]; //cost[]用来记录该点到其父节点的距离
void addMSTedge(int x,int y,int len)
{
MSTe[cnt].x = y;
MSTe[cnt].len = len;
MSTe[cnt].next = head[x];
head[x] = cnt++;
}
int root(int x)
{
if(parent[x] == -1)return x;
else return parent[x] = root(parent[x]);
}
void merge(int x,int y)
{
x = root(x);
y = root(y);
parent[x] = y;
}
void kruskal()
{
cnt = 0; //MST中边的下标
int jishu = 0; //计数
while(!Q.empty())
{
edge t = Q.top();
Q.pop();
if(root(t.x) != root(t.y))
{
merge(t.x,t.y);
jishu++;
addMSTedge(t.x,t.y,t.len);
addMSTedge(t.y,t.x,t.len);
}
if(jishu == n-1) //MST中有了n-1条边
break;
}
}
void roottree() //建立有根树
{
int flag[INF]; //标记MST的该点是够遍历过
MEM(flag,0);
MEM(dis,0);
MEM(father,-1);
MEM(cost,0);
queue<int>que;
while(!que.empty())
que.pop();
que.push(1); //以1为根利用bfs建立有根树
flag[1] = 1;
dis[1] = 0;
while(!que.empty())
{
int t = que.front();
que.pop();
for(int i = head[t] ; i != -1; i = MSTe[i].next)
{
int temp = MSTe[i].x; //该边的末点
if(flag[temp] == 0)
{
flag[temp] = 1; //标记该点已经遍历过了
father[temp] = t; //更新父节点
cost[temp] = MSTe[i].len;
dis[temp] = dis[t] + 1; //层数加一
que.push(temp);
}
}
}
}
void solve(int x,int y)
{
int maxx = -1,maxy = -1; //初始化两个点到根节点的路的最大边权
if(dis[x] > dis[y]) //如果x的层数大于y的,即x在y下面
{
while(dis[x] > dis[y])
{
maxx = max(maxx,cost[x]); //更新这条路的最大边权
x = father[x];
}
}
else if(dis[y] > dis[x])
{
while(dis[y] > dis[x])
{
maxy = max(maxy,cost[y]); //更新这条路的最大边权
y = father[y];
}
}
//此时x,y层数相同,然后就可以两边同时向上遍历，更快
while(x != y) //当x,y的祖先相同时，就结束算法
{
maxx = max(maxx,cost[x]); //两个节点同时往上走
x = father[x];
maxy = max(maxy,cost[y]);
y = father[y];
}
printf("%d\n",max(maxx,maxy));
}
int main()
{
int nnn= 0;
while(scanf("%d%d",&n,&m) != EOF)
{
if(nnn++ != 0)
printf("\n");
MEM(parent,-1);
MEM(head,-1);
MEM(MSTe,0);
while(!Q.empty())
Q.pop();
for(int i = 1; i <= m ; i++)
{
edge t;
scanf("%d%d%d",&t.x,&t.y,&t.len);
Q.push(t);
}
kruskal(); //求最小生成树MST
roottree(); //把MST变成有根树
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
solve(x,y);
}
}
return 0;
}
次小生产树
另一类相关问题就是次小生成树了。题目的要求就是求出权值第二小的最小生成树的值（若最小有两种方案则值相等），对于次小生成树都有一种暴力做法就是枚举所有不在最小生成树中的边这个能求出答案但是复杂度太高往往无法承受，下面给出一种 O(n^2)算法。
1.求出最小生成树。
2.找出每个点对之间的最大边长 。
3.枚举所有不在最小生成树上的边设(u,v),删除原来u,v之间最大边长，加上这条边的边长，更新答案。
例题
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
const int N=105;
int mat[N][N];
const int inf=99999999;
int father[N];
struct Edge
{
int a,b,c;
}edge[N*N];
int mst_edge[N];
bool cmp(Edge &a,Edge &b)
{
if(a.c<b.c)
return true;
return false;
}
int find(int u)
{
while(father[u]>=0)
{
u=father[u];
}
return u;
}
void Union(int fa,int fb)
{
if(father[fa]<father[fb])
{
father[fa]=father[fa]+father[fb];
father[fb]=fa;
}
else
{
father[fb]=father[fa]+father[fb];
father[fa]=fb;
}
}
void krusk()
{
memset(father,-1,sizeof(father));
memset(mst_edge,0,sizeof(mst_edge));
sort(edge+1,edge+1+m,cmp);
int ans=0;
int k=0;
for(int i=1;i<=m&&k<n-1;i++)
{
int a=find(edge[i].a);
int b=find(edge[i].b);
if(a!=b)
{
Union(a,b);
k++;
ans+=edge[i].c;
mst_edge[k]=i;
}
}
for(int i=1;i<=n-1;i++)
{
int ans2=0,k2=0;
memset(father,-1,sizeof(father));
for(int j=1;j<=m;j++)
{
if(j==mst_edge[i])
continue;
int a=find(edge[j].a),b=find(edge[j].b);
if(a!=b)
{
Union(a,b);
k2++;
ans2+=edge[j].c;
}
}
if(k2!=n-1)
{
continue;
}
if(ans2==ans)
{
printf("Not Unique!\n");
return ;
}
}
printf("%d\n",ans);
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--)
{
scanf("%d%d",&n,&m);
memset(edge,0,sizeof(edge));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
}
krusk();
}
return 0;
}
还是很好想的
好了差不多讲完了，其实还有最小树形图（zhuliu算法），最小限制生成树，k度最小生成树（参见2004汪汀国家队论文）。感觉这些都比较难等以后掌握好了在写总结吧。。。