先把必要的边连接在一起，将一条边的顶点合并在同一个集合中，从剩余的边中选择权值最少的使图连通即可。
以下是我的代码：
#include<iostream>
#define maxn 2007
#define maxm 10007
using namespace std;
typedef struct
{
long u,v,w;
}edge;
long n,m,cnt,num,ans,f[maxn];
edge e[maxm];
void Qsort(long l,long r)
{
long i=l,j=r,m=e[(l+r)/2].w;
do{
while(e[i].w<m) i++;
while(e[j].w>m) j--;
if(i<=j)
{
edge t=e[i];e[i]=e[j];e[j]=t;
i++;j--;
}
}while(i<=j);
if(l<j) Qsort(l,j);
if(i<r) Qsort(i,r);
}
long Getf(long x)
{
if(f[x]==x) return x;
f[x]=Getf(f[x]);
return f[x];
}
int main()
{
cin>>n>>m;
for(long i=1;i<=n;i++) f[i]=i;
ans=num=cnt=0;
for(long i=1;i<=m;i++)
{
long ra,rb,rc,rd;
cin>>ra>>rb>>rc>>rd;
if(ra==1)
{
ans+=rd;
long fx=Getf(rb),fy=Getf(rc);
if(fx!=fy)
{
f[fx]=fy;
num++;
}
}
else
{
cnt++;
e[cnt].u=rb;e[cnt].v=rc;e[cnt].w=rd;
}
}
// Input
Qsort(1,cnt);
// Qsort
for(long i=num,j=1;i<n-1;j++)
{
long fx=Getf(e[j].u),fy=Getf(e[j].v);
if(fx!=fy)
{
f[fx]=fy;
ans+=e[j].w;
i++;
}
}
cout<<ans<<endl;
return 0;
}
posted on 2010-10-17 13:37
lee1r 阅读(294)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论