还有克鲁斯卡尔

poj - 1258
居然不说是多组样例.......

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 100005
int n;
int Count;
int pre[100005];
struct node
{
    int v;
    int w;
    int edge;
}s[100005];
bool cmp(node a,node b)
{
    return a.edge<b.edge;
}
void unit()
{
    for(int i=0;i<INF;i++)
    {
        pre[i]=i;
    }
}
int find(int x)
{
    if(pre[x]==x)
    return x;
    else
    return find(pre[x]);
}
int Union(int a,int b)
{
    int X=find(a);
    int Y=find(b);
    if(X!=Y)
    {
        pre[X]=Y;
    }
     pre[a]=find(a);
pre[b]=find(b);
}
void krual()
{
    int sum=0;
    int num=0;
    for(int i=0;i<Count;i++)
    {
        if(find(s[i].v)!=find(s[i].w))
        {
            sum=sum+s[i].edge;
            num++;
            Union(find(s[i].v),find(s[i].w));
        }
        if(num>=n-1)
        {   printf("%d\n",sum);
        break;
    }
    }
}
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
    Count=0; 
   int x;
   unit();
   for(int i=0;i<n;i++)
   {
    for(int  j=0;j<n;j++)
    {
        if(i>j)
        {
        scanf("%d",&s[Count].edge);
        s[Count].v=i;
        s[Count].w=j;
        Count++;
        }
        else
        scanf("%d",&x);
        
    }
   }    
   sort(s,s+Count,cmp);
   krual();
   }
} 
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容