求最小生成树两个算法
1、prim算法
首先设图G，点集V。
任取一个结点v1，加入最小生成树点集VT={v1}，|VT|=k=1
在V-VT中选取某个vi∈VT邻接的结点vj，使得边（vi，vj）权最小，添加vj到VT，k++.
重复上一步直到k=|V|
（以下是通俗说法）
取一个起点，之后每次取一个点 使该点到已经取过的某一点的距离最小，直到所有点都取到为止。
此算法用邻接矩阵比较方便
2、kruskul算法
设图G，边集={e1,e2,e3......}
在G中选取最小权边e1，设i为已选取边数，i=1
while（i!=n-1）
{
在G中选取不同于已选边的最小权边ei，使它和已选边不构成回路
i++；
}
此算法用邻接表比较方便
先对边权排序，从小到大选择符合条件的合并，直到找到n-1条边为止。
hdu1233 还是畅通工程
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;
int n,ans,vis[105],d[105],e[105][105];
void prim()
{
int i,j,tmp,p;
memset(vis,0,sizeof vis);
for(i=0;i<=n;i++)
d[i]=e[1][i];
d[1]=0;
for(i=1;i<=n;i++)
{
tmp=inf;
for(j=1;j<=n;j++)
{
if(!vis[j]&&tmp>d[j])
{
tmp=d[j];
p=j;
}
}
vis[p]=1;
for(j=1;j<=n;j++)
{
if(!vis[j]&&e[j][p]<d[j])
{
d[j]=e[j][p];
}
}
}
ans=0;
for(i=1;i<=n;i++)
ans+=d[i];
}
int main()
{
int a,b,w,i;
while(scanf("%d",&n)&&n)
{
int tmp=n*(n-1)/2;
for(i=0;i<tmp;i++)
{
scanf("%d%d%d",&a,&b,&w);
e[a][b]=e[b][a]=w;
}
prim();
printf("%d\n",ans);
}
return 0;
}
hdu1863 畅通工程
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;
struct node
{
int x,y,w;
}e[5010];
int n,m,ans,r[105];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int root(int a)
{
if(r[a]==a) return a;
return r[a]=root(r[a]);
}
void kruskal()
{
int i,ra,rb,edge=0;
for(i=0;i<m;i++)
{
ra=root(e[i].x);
rb=root(e[i].y);
if(ra==rb) continue;
else
{
if(ra>rb)
r[rb]=ra;
else r[ra]=rb;
ans+=e[i].w;
edge++;
if(edge==n-1)
{
printf("%d\n",ans);
return;
}
}
}
printf("?\n");
return ;
}
int main()
{
int i;
while(scanf("%d%d",&m,&n)&&m)
{
for(i=0;i<=n;i++)
r[i]=i;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
}
sort(e,e+m,cmp);
ans=0;
kruskal();
}
return 0;
}
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;
struct node
{
int x,y;
double w;
}e[5050];
double ans;
int n,m,r[110],x[110],y[110];
bool cmp(node a,node b)
{
return a.w<b.w;
}
double dis(int a,int b,int c,int d)
{
return sqrt(((a-c)*(a-c)+(b-d)*(b-d))*1.0);
}
int root(int a)
{
if(r[a]==a) return a;
return r[a]=root(r[a]);
}
void kruskal()
{
int i,ra,rb,edge=0;
for(i=0;i<n;i++)
r[i]=i;
for(i=0;i<m;i++)
{
ra=root(e[i].x);
rb=root(e[i].y);
if(ra==rb||e[i].w<10) continue;
if(e[i].w>1000) break;
else
{
if(ra>rb)
r[rb]=ra;
else r[ra]=rb;
ans+=e[i].w;
edge++;
if(edge==n-1)
{
printf("%.1lf\n",ans*100);
return ;
}
}
}
printf("oh!\n");
return;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
m=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
e[m].x=i;
e[m].y=j;
e[m++].w=dis(x[i],y[i],x[j],y[j]);
}
}
sort(e,e+m,cmp);
ans=0;
kruskal();
}
return 0;
}
hdu1879 继续畅通工程
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;
struct node
{
int x,y,w;
}e[5010];
int n,m,ans,r[110];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int root(int a)
{
if(r[a]==a) return a;
return r[a]=root(r[a]);
}
void merge(int a,int b)
{
int ra,rb;
ra=root(a);
rb=root(b);
if(ra!=rb)
r[ra]=rb;
}
void kruskal()
{
int i,ra,rb;
for(i=0;i<m;i++)
{
ra=root(e[i].x);
rb=root(e[i].y);
if(ra==rb) continue;
else
{
if(ra>rb)
r[rb]=ra;
else r[ra]=rb;
ans+=e[i].w;
}
}
return;
}
int main()
{
int tmp,a,b,c,d,i;
while(scanf("%d",&n)&&n)
{
for(i=0;i<=n;i++)
r[i]=i;
int tmp=n*(n-1)/2;
m=0;
for(i=0;i<tmp;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(d==1)
merge(a,b);
else
{
e[m].x=a;
e[m].y=b;
e[m++].w=c;
}
}
sort(e,e+m,cmp);
ans=0;
kruskal();
printf("%d\n",ans);
}
return 0;
}
最小生成树基础题目之畅通工程系列,布布扣,bubuko.com
原文：http://blog.csdn.net/u011032846/article/details/22087463