注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2912  

2010-02-27 23:08:52|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一道并差集的经典题目,枚举裁判,然后看是否有矛盾,而判断的行数就是其他有矛盾的最大行数
问题就麻烦在矛盾的判断上,需要一个相应的rank值,来判定元素和父节点的关系,由于一开始union的时候公式没有弄清楚,wa了几次,囧~
#include<cstdio>
#include<cstring>
int a[2002][2],n,m,f[501],rank[501];
char c[2002];
int char2int(char cc){
    if(cc=='=')
      return 0;
    if(cc=='<')
      return 2;
    return 1;
}
int find(int k){
    if(f[k]<0)
      return k;
    int temp=f[k];
    f[k]=find(f[k]);
    rank[k]=(rank[k]+rank[temp])%3;
    return f[k];
}
void uni(int k1,int k2,int k3){
     int a1=find(k1),a2=find(k2),temp=f[a1]+f[a2];
     if(f[a1]<f[a2]){
       f[a2]=k1;
       rank[a2]=(6-rank[k2]-k3)%3;
       f[a1]=temp;
     }
     else{
       f[a1]=k2;
       rank[a1]=(3-rank[k1]+k3)%3;
       f[a2]=temp;
     }
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
      for(int i=0;i<m;i++)
        scanf("%d%c%d",&a[i][0],&c[i],&a[i][1]); 
      int maxt=0,sum=0,t=0;
      for(int i=0;i<n;i++){
        memset(f,-1,sizeof(f));
        memset(rank,0,sizeof(rank));
        int mark=0;
        for(int j=0;j<m;j++)
         if(a[j][0]!=i&&a[j][1]!=i){
          int a1=find(a[j][0]),a2=find(a[j][1]),a3=char2int(c[j]);
          if(a1==a2&&(rank[a[j][0]]+3-rank[a[j][1]])%3!=a3){
            mark=1;
            if(maxt<j+1)
              maxt=j+1;
            break;
          }
          if(a1!=a2)
            uni(a[j][0],a[j][1],a3);
        }
        if(!mark){
          sum++;
          if(sum>1)
            break;
          t=i;
        }
      }
      if(!sum)
        printf("Impossible\n");
      else if(sum>1) printf("Can not determine\n");
      else printf("Player %d can be determined to be the judge after %d lines\n",t,maxt);
    }
    return 0;
}

  评论这张
 
阅读(707)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017