心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

先把必要的边连接在一起,将一条边的顶点合并在同一个集合中,从剩余的边中选择权值最少的使图连通即可。
以下是我的代码:

#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)  编辑 收藏 引用 所属分类: 题目分类:图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理