首页 > 代码库 > 又见关系并查集 以POJ 1182 食物链为例
又见关系并查集 以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 <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。