The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HOJ 3367 Pseudoforest 并查集

这题其实当时就应该想到,但只想到kruskal的程度,觉得不对,就没敢敲。看了下解题报告,原来可以巧妙的利用一下n号集合,怎么说呢,把边从大到小排序,然后像做最大生成树那样增加边。
1.如果两个顶点在同一集合,就把这个集合同一挂到n号集合下面去,由于题目中没有n这个点,所以挂在n下的就算找到圈了。
2.如果两个顶点不在同一集合,且两个顶点都不在n集合,那么请随意:-)。
3.如果有一个顶点在n集合中,这里要特别注意,害我RE了无数回,要把不是n的那个集合挂到n下面去。想想嘛,本来找到圈了,结果挂到0-n-1下面,又会认定为没有圈了。
(此题算法参考了标程,但是标程写得实在太挫了,好像故意要让人看不懂似的,跟tc里的变态们一个样,难道标程就不应该写的友好一点?bsz)

#include<iostream>
#include
<algorithm>
#include
<cstdio>
using namespace std;

struct node
{
    
int a;
    
int b;
    
int v;
    
bool operator<(node other)
    
{return v<other.v;}
}
e[2000010];
int ans;

int f[100100];
int r[100000];
int n,m;

int find(int x)
{
    
if(f[x]==x)
        
return x;
    
else f[x]=find(f[x]);
    
return f[x];
}





int main()
{
    
//freopen("Pseudoforest.in","r",stdin);
    
    
int i,j;
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        ans
=0;
        
if(n==0&&m==0break;
        
for(i=0;i<=n;i++)
            f[i]
=i;
        
for(i=0;i<m;i++)
            scanf(
"%d%d%d",&e[i].a,&e[i].b,&e[i].v);
        sort(e,e
+m);
        
for(i=m-1;i>=0;i--)
        
{
            
int a=find(e[i].a);
            
int b=find(e[i].b);
            
if(a>b)
                swap(a,b);
            
if(a!=b)
            
{
                ans
+=e[i].v;
                f[a]
=b;
            }

            
else if(a==b&&b!=n)
            
{
                ans
+=e[i].v;
                f[a]
=n;
            }

        }

        printf(
"%d\n",ans);
    }

    
return 0;
}

posted on 2010-04-10 00:45 abilitytao 阅读(969) 评论(0)  编辑 收藏 引用


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