【并查集】食物链

2019-11-06 06:25:40

字体：大中小

来源：转载

供稿：网友

题目传送门：http://codevs.cn/PRoblem/1074/

现在才发现我这么蒟蒻，并查集都不怎么会用啊！！！

这道题似乎用了一个很巧妙（估计是我太弱）的东西，就是用 i , i+n , i+n*2 来表示 i 在 A B C 三个种类，似乎是可以轮换的

然后每读入一次先验证是否是假话，不是的话就合并（好像是废话）

具体见代码吧

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define LL long longint fa[150005],n,m,x,y,z,ans;int find(int x){ if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x];}void unite(int x,int y){ x=find(x); y=find(y); if (x==y) return; fa[x]=y;}int main(){ cin>>n>>m; for (int i=1;i<=n*3;i++) fa[i]=i; for (int i=1;i<=m;i++){ cin>>z>>x>>y; if (x<0 || x>n || y<0 ||y>n){ ans++; continue; } if (z==1){ if (find(x)==find(y+n) || find(x)==find(y+n*2)){//x与y一样时显然不能互相吃来吃去 ans++; continue; } else{ unite(x,y); unite(x+n,y+n); unite(x+n*2,y+n*2); } } if (z==2){ if (find(x)==find(y) || find(x)==find(y+n*2)){//x吃y时x显然不与y一样，也不能是y吃x ans++; continue; } else{ unite(x,y+n); unite(x+n,y+n*2); unite(x+n*2,y); } } } cout<<ans;}

上一篇：高斯消元法模板

下一篇：1126: 布尔矩阵的奇偶性