# 最小生成树的相关算法

1、单次询问

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];
{
++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)
}
double ans;
kruskal(ans);
printf("Scenario #%d\n",topt);
printf("Frog Distance = %0.3lf\n\n",ans);
}
return 0;
}

#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);

}

#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、多次查询

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;
priority_queue<edge>Q;		//存储整个图的边

//将MST变成有根树时使用的变量
int father[INF],dis[INF];			//fatehr[]用来记录该节点在有根树中的父节点，dis[]用来记录该点的层数
int cost[INF];				//cost[]用来记录该点到其父节点的距离

{
MSTe[cnt].x = y;
MSTe[cnt].len = len;
}
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++;
}
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(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;
}

1.求出最小生成树。

2.找出每个点对之间的最大边长 。

3.枚举所有不在最小生成树上的边设(u,v),删除原来u,v之间最大边长，加上这条边的边长，更新答案。

1679 poj

#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;
}