带权并查集专题
算是一个模板题吧
给出[l,r]的区间和，相当于s[r]-s[l]
一旦已经知道了 s[a]-s[b],s[b]-s[c]，显然再给出一条[a,c]就可以判断"账本的真假"了
将每条这样的信息(l,r,w)，l,r放入一个集合中，
用并查集来维护，并维护cha[l]=s[root]-s[l],cha[r]=s[root]-s[r]
若 l,r已经在同一个集合中，就直接查询cha[l]-cha[r]，判读与w是否相等
合并操作是灵魂
实话说如果没有对并查集合并操作和路径压缩理解够深刻 是不能写出来的
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=505;
int T;
int fa[maxn],val[maxn];
int find(int x){
if(fa[x]==x)return x;
else {
int oldfa=fa[x];
fa[x]=find(fa[x]);
val[x]+=val[oldfa];
return fa[x];
}
}
void solve();
int main(){
cin>>T;
while(T--)solve();
return 0;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)
fa[i]=i,val[i]=0;
bool cmp=1;
while(m--){
int x,y,z;
cin>>x>>y>>z;
x--;
int fx=find(x),fy=find(y);
if(fx!=fy){
fa[fy]=fx;
val[fy]=val[x]-val[y]-z;
}
else if(val[x]-val[y]!=z)cmp=0;
}
if(cmp)cout<<"true"< 
每次给出两个昆虫的关系（异性关系），然后发现这些条件中是否有悖论
和上一个题目差不多 维护x->rootx 的距离就好
#include
const int maxn = 2000 + 10;
int pre[maxn];
int r[maxn]; // 与根节点的关系，如果值为1则为异性如果为0则为同性
int find(int x) {
int t = pre[x];
if (pre[x] != x) {
pre[x] = find(pre[x]);
r[x] = (r[x] + r[t]) % 2; // 更新关系
}
return pre[x];
}
int main() {
// freopen("input.txt", "r", stdin);
int flag;
int kase = 0;
int T;
int x, y;
int n, m;
scanf("%d", &T);
while(T--) {
flag = 1;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
pre[i] = i;
r[i] = 0;
}
while(m--) {
scanf("%d%d", &x, &y);
if (!flag) continue;
int rx = find(x);
int ry = find(y);
if (rx == ry) {
if ((r[x] - r[y]+2) % 2 == 0) {
flag = 0;
}
}
else {
pre[ry] = rx;
r[ry] = (r[x] - r[y] + 1) % 2;
}
}
printf("Scenario #%d:\n",++kase);
if(flag)
printf("No suspicious bugs found!\n\n");
else
printf("Suspicious bugs found!\n\n");
}
return 0;
}
这个题是上面的题型的升级版 首先找到规律
0吃1
1吃2
2吃0（2吃3）
发现后面减去前面始终为1 所以就是 被吃 减 吃==1
剩下的就差不太多了
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=5e4+5;
int n,m,ans;
int fa[maxn],val[maxn];
int find(int x){
if(x==fa[x])return x;
int oldfa=fa[x];
fa[x]=find(fa[x]);
val[x]=(val[x]+val[oldfa])%3;
return fa[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i,val[i]=0;
for(int i=1;i<=m;i++){
int c,x,y;
cin>>c>>x>>y;
if(x>n||y>n||(c==2&&x==y)){
ans++;continue;
}
int fx=find(x),fy=find(y);
if(c==1){
if(fx!=fy){
fa[fy]=fx;
val[fy]=(val[x]-val[y]+3)%3;
}else if((val[y]-val[x]+3)%3)
ans++;
}else{
if(fx==fy){
if(((val[y]-val[x]+3)%3)!=1)
ans++;
}
else{
fa[fy]=fx;
val[fy]=(val[x]-val[y]+1+3)%3;
}
}
}
cout< 
因为朋友之间是双向边 只要在合并的时候维护一下集合的最小值就好 最后每个集合只要保证有一个最小的人去贿赂就好
思考：如果是单向边的话 那就要tarjan缩点 然后对每个缩完点入度为0的点中找出最小的一个 累加