又见关系并查集以POJ 1182 食物链为例 - c++编程基础

TOP

又见关系并查集以POJ 1182 食物链为例

2015-07-20 18:01:24 来源: 作者: 【大中小】浏览:2次

Tags：关系查集 POJ 1182 食物链

简单的关系并查集一般很容易根据给出的关系搞出一个有向的环，那么两者之间的关系就变成了两者之间的距离。

对于此题：

若u，v不在一个集合内，则显然此条语句会合法（暂且忽略后两条，下同）。

那么将fu 变为 fv的儿子时需加一条权值为 w 的边，w 满足(w + ru)%3 = (rv+ (D == 1? 0 : 1))%3（ru，rv分别为u，v与fv的关系，即距离）。

之所以在D == 2时加 1，是因为u吃v表明着u到fv的距离比v到fv的距离大1。

同理，D == 1时，表明两者到fv的距离应该相等。

若u，v在一个集合内，只需要判断ru%3 == (rv+(D == 1?):1))%3 是否成立即可。

不过这个题数据略坑啊，写成多组输入的根本过不了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f using namespace std; struct N { int fa,re; } st[50010]; int Find(int x,int &R) { int f,re = 0; f = x; while(f != st[f].fa) { re = (re+st[f].re)%3; f = st[f].fa; } R = re; int tre = 0,temp,tf; while(x != st[x].fa) { tf = st[x].fa; temp = st[x].re; st[x].re = (re-tre+3)%3; tre = (tre+temp)%3; st[x].fa = f; x = tf; } return f; } bool Merge(int w,int u,int v) { int ru,rv; int fu = Find(u,ru); int fv = Find(v,rv); if(fu != fv) { st[fu].fa = fv; if(w == 2) st[fu].re = ((rv+1)%3 - ru + 3)%3; else st[fu].re = (rv%3- ru + 3)%3; } else { if(w == 1 && ru != rv) return false; if(w == 2 && ru != (rv+1)%3 ) return false; } return true; } int main() { int n,k; int i,j,u,v,w; scanf("%d %d",&n,&k); { for(i = 1; i <= n; ++i) st[i].fa = i,st[i].re = 0; int ans = 0; while(k--) { scanf("%d %d %d",&w,&u,&v); if(u > n || v > n || (w == 2 && u == v)) { ans++; continue; } if(Merge(w,u,v) == false) { ans++; } } printf("%d\n",ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 4901 The Romantic Hero(二维..	下一篇：poj 2442

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: