Vijos P1531 食物链

本文主要是介绍Vijos P1531 食物链，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

没看懂偏移向量和拆点

用的带权并查集水过去的

注意先判断 是否大于n

可能有 1 n+1 n+1

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 50000+10;int fa[MAXN],fv[MAXN];
int find(int x)
{if(fa[x]!=x) {int t=fa[x];fa[x]=find(fa[x]);fv[x]+=fv[t];}return fa[x];
}
void link(int x,int y,int opt)
{int fx=find(x);int fxv=fv[x];int fy=find(y);int fyv=fv[y];int v=fxv-fyv+opt;v=(v%3+3)%3;fa[fy]=fx;fv[fy]=v;
}int n,k;
int query(int x,int y,int opt)
{if(x>n||y>n) return 0;if(x==y) {if(opt==0) return 2;return 0;}if(find(x)!=find(y)) return 1;if(((fv[x]-fv[y])%3+3)%3==(3-opt)%3) return 2;else return 0;
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++) fa[i]=i;int cnt=0;for(int i=1;i<=k;i++){int opt,x,y;scanf("%d %d %d",&opt,&x,&y);opt--;int t=query(x,y,opt);if(t==1) link(x,y,opt);if(t==0) cnt++;}cout<<cnt;return 0;
} 

这篇关于Vijos P1531 食物链的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---