又见关系并查集以POJ 1182 食物链为例-白红宇

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

阅读量：7169 次

发布时间：2019-06-29

本文共 1577 字，大约阅读时间需要 5 分钟。

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

对于此题：

若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 0x3f3f3f3fusing 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;}