题目连接:http://poj.org/problem?id=1182
中文题就不说题意了。加权并查集,处理每个节点时,除了保存其父节点的信息,同时要保存该节点与父节点的关系,0表示和父节点为同类,1表示父节点吃子节点,2表示子节点吃父节点。或者说保存的是该节点的动物在食物链中的层数,因为只有ABC三类动物,所以层数为0,1,2,在运算过程当中调整为大于零的整数后对3取模即可。这样问题的核心就是对层数的处理了。处理方式详见代码。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <memory.h> using namespace std; int n,m; int ans; int p[110000],ch[110000]; int find(int k) { if (p[k]==k) return k; else { int t=find(p[k]); ch[k]=(ch[k]+ch[p[k]]) % 3; p[k]=t; return t; } } void check(int x,int y,int d) { int tp=find(x); int tq=find(y); if (x>n || y>n) { ans++; return; } if (tp==tq) { if ((ch[x]-ch[y]+3)%3!=d) ans++; return; } p[tp]=tq; ch[tp]=(ch[y]-ch[x]+6+d)%3; return; } int main() { //freopen("a.in","r",stdin); scanf("%d%d",&n,&m); memset(ch,0,sizeof ch); memset(p,0,sizeof p); for (int i=0; i<=n; i++) p[i]=i; ans=0; int x,y,z; for (int i=1; i<=m; i++) { scanf("%d%d%d",&z,&x,&y); z--; check(x,y,z); } printf("%d\n",ans); return 0; }