避圈法
英文名称：
kruskal
最小支撑树问题
主要思想：
开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。
算法的具体步骤：
第一步：令i=1，Ei=Φ.( Φ表示空集)
第二步：选一条边ei ∈ E\Ei-1,使（V，Ei-1∪{e}）不含圈的所有边e（ei ∈ E\Ei-1）中权最小的边。令Ei=Ei-1∪{e}，如果这样的边不存在，则T=（V，Ei-1）是最小树。
第三步：把i换成i+1，转入第二步。
例题：NYOJ 502 筹建工程
筹建工程
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
- 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本(道路是双向的)。现请你编写程序,计算出全省畅通需要的最低成本。
- 输入
- 测试输入包含若干测试用例。第一行一个整数 T (T <= 5) 表示测试用例数量,每个测
试用例的第 1 行给出评估的道路条数 N、村庄数目 M ( 1 <= M < 100,0 <= N <= M *( M-1) /2),随后的 N 行对应村庄间道路的成本,每行给出三个正整数,依次是两个村庄的编号(每对村庄至多出现一次),以及此两村庄间道路的成本( 也是正整数 )。
为简单起见,村庄从 1 到 M 编号。 - 输出
- 对每个测试用例,在 1 行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出 No solution。
- 样例输入
-
2 3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2
- 样例输出
-
3 No solution
- 程序写的比较繁琐，开始先用并查集查找是否能形成通路，不能则直接返回
- 这个地方曾经出过错，开始的时候优先队列的清零函数写在程序最后（这本来就是个错误！）
- 然后程序continue；之后造成优先队列没有清空，进而数据影响最后的结果！
- 以后注意程序开始while（）之后清零该清零的，
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
int x,y;
int w;
node(int x,int y,int w):x(x),y(y),w(w){}//这是构造函数 ，方便编程使用
};
bool operator < (const node a,const node b)//重载了优先队列的优先性
{
return a.w > b.w;
}
priority_queue<node>q;
int pa[105];
int find(int x){return pa[x]==x ? x :pa[x]=find(pa[x]);}//并查集主要函数
int main()
{
// freopen("in.txt","r",stdin);
int T,N,M,i,a,b;
int c;
scanf("%d",&T);
while(T--)
{
while(!q.empty())q.pop();
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)pa[i]=i;
for(i=1;i<=N;i++)
{
int x,y;
scanf("%d%d%d",&a,&b,&c);
if(a==b)continue;
x=find(a);y=find(b);
if(x!=y)pa[x]=y;
q.push(node(a,b,c));
}
if(M==1)
{
printf("0\n");
continue;
}
if(N<M-1)
{
printf("No solution\n");
continue;
}
int num=0;
memset(pa,0,sizeof(pa));
for(i=1;i<=M;i++)if(pa[i]==i)num++;
if(num>1)
{
printf("No solution\n");
continue;
}
for(i=1;i<=M;i++)pa[i]=i;
num=1;
int res=0;
while(num<M)
{
int x,y;
x=find(q.top().x);
y=find(q.top().y);
if(x!=y){res+=q.top().w;num++;pa[x]=y;}
q.pop();
}
printf("%d\n",res);
}
return 0;
}
可以将kruskal() （避圈法）写成函数模板，（下面的代码）
在题目改变的时候尽量不改变模板的前提下通过主函数的修改达到解题目的，
比如此题中，如果所有道路不能构成连通图的情况，如果更改kruskal（）函数需要加上一个变量 t ，记录一共使用的道路条数，
如果 t 小于村庄减一，那么就 不能完成，修改主函数时需要调用先用一次并查集，排除不能联通的情况
下面看代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#define FLAG 0
using namespace std;
int p[110];//并查集数组
struct stu
{
int u,v,w;
}r[110];
bool cmp(stu a,stu b)
{
return a.w<b.w;
}
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int kruskal(int n,int m)//n是点的个数，m是线(道路)的个数
{
int sum=0,i;
for(i=1;i<=n;i++){p[i]=i;}//初始化并查集
sort(r,r+m,cmp);//把线按照费用的由小到大排序
for(i=0;i<m;i++)//从0开始遍历，这里要求主函数从0开始接收
{
int x=find(r[i].u);
int y=find(r[i].v);
if(x!=y){sum+=r[i].w;p[x]=y;}
}
return sum;//返回的是总费用
}
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int T,a,b,i,j;
cin>>T;
while(T--)
{
cin>>a>>b;//道路a、村庄的数目b
for(i=0;i<a;i++)
{
cin>>r[i].u>>r[i].v>>r[i].w;
}
if(a<b-1){cout<<"No solution"<<endl;continue;} //特殊情况
for(i=1;i<=b;i++)p[i]=i;//先用并查集看这些道路能否有可能把所有的村庄连在一起
for(i=0;i<a;i++)
{
int x=find(r[i].u);
int y=find(r[i].v);
if(x!=y)p[x]=y;
}
int term=0;
for(i=1;i<=b;i++)
if(p[i]==i)term++;
if(term>1)
{
cout<<"No solution"<<endl;
}
else //如果可以连在一起，就调用kruskal函数；
{
cout<<kruskal(b,a)<<endl;
}
}
return 0;
}