infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2492
ms很邪恶 很ws的题目,题目给出了n组bug 相好的记录让
你在一大堆bug中让你找出可疑的同性恋者。够邪恶吧!!
简单并的并查集。

Source Code

Problem: 2492
User: lovecanon
Memory: 228K
Time: 735MS
Language: C++
Result: Accepted
#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
int father[2000+1],mark[2000+1],rank[2000+1];
int find(int t){
    
int tmp=t,flag=mark[t];
    
while(father[tmp]!=tmp){
        flag
^=mark[father[tmp]];
        tmp
=father[tmp];
    }
    father[t]
=tmp;
    mark[t]
=flag;
    
return tmp;
}
int main()
{
    
int i,T,cases=1;
    scanf(
"%d",&T);
    
while(T--){
        
int N,M;
        scanf(
"%d%d",&N,&M);
        
for(i=1;i<=N;i++) {father[i]=i;mark[i]=0;rank[i]=0;}
        
int a,b,flag=0;
        
while(M--){
            scanf(
"%d%d",&a,&b);
            
int x=find(a),y=find(b);
            
if(flag==0 && x==&& mark[a]==mark[b]) flag=1;
            
else if(flag==0 && x!=y){
                
if(rank[x]>rank[y]){
                    father[x]
=y;
                    mark[x]
=!(mark[a]^mark[b]);
                }
                
else{
                    father[y]
=x;
                    mark[y]
=!(mark[a]^mark[b]);
                    
if(rank[x]==rank[y]) rank[x]++;
                }
            }
        }
        
if(flag==1) printf("Scenario #%d:\nSuspicious bugs found!\n\n",cases);
        
else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",cases);
        cases
++;
    }
    
//system("pause");
    return 0;
}
posted on 2008-10-24 01:47 infinity 阅读(942) 评论(1)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 2492 a bug's life. 2009-08-30 21:35 aa
我说这题目什么意思,一打开,就是“该页面含有敏感关键词,您无权访问该页面!”,原来如此!  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理