Yiner的ACM

成长的痕迹
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

并查集 HDU1863
这题把前面两道题组合到了一起 判断最小生成树 和是否是一棵树
#include<iostream>
#include
<stdio.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

int father[101];
bool flags[101];

struct country
{
    
int first;
    
int second;
    
int value;
}
a[5001];

bool cmp(country x,country y)
{
    
return x.value<y.value;
}


int makeset(int n)
{
    
for(int i=1;i<=n;i++)
    father[i]
=i;
}


int findset(int x)
{
    
if(father[x]!=x)
     
{
         father[x]
=findset(father[x]);
     }

     
return father[x];
}


int Union(int a,int b)
{
    
int x=findset(a);
    
int y=findset(b);
    
if(x==y)
    
return 1;
    
else
    
{
        father[x]
=y;
    
return 0;
    }

}


int main()
{
    
int n,m;
    
while(~scanf("%d%d",&n,&m))
    
{
        
if(n==0)
        
break;
        
int sum=0;
        makeset(m);
        memset(flags,
false,sizeof(flags));
        
for(int i=1;i<=n;i++)
        
{

            scanf(
"%d%d%d",&a[i].first,&a[i].second,&a[i].value);

        }

        sort(a
+1,a+n+1,cmp);


        
for(int i=1;i<=n;i++)
        
{

            
if(Union(a[i].first,a[i].second)==0)
            
{
                sum
=sum+a[i].value;
            }

        }


        
for(int i=1;i<=m;i++)
        
{
            flags[findset(i)]
=true;
        }


        
int k=0;
        
for(int i=1;i<=m;i++)
        
{
            
if(flags[i]==true)
            k
++;
        }


        
if(k!=1)
        printf(
"?\n");
        
else
        printf(
"%d\n",sum);
    }

    
return 0;
}

posted on 2011-03-31 09:21 Yiner 阅读(678) 评论(0)  编辑 收藏 引用 所属分类: 并查集


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