带权并查集+二分图解法

带权并查集 分析A，B之间的相对距离，可以得到rnk[fa] = rnk[A]+x-rnk[B]。 注意到这时，对于原来的A的树，只更新了fa跟结点的权值， 那么其它结点的更新在查找的那一步里面实行了。
维护是相对距离

一开始 ab之间关系 a到b是s 在 fa fb 不一样是 我们可以当 a到fa b到fb 还有 a到b距离s 是向量 那么 rnk[fb]=rnk[a]-rnk[b]+s

种类并查集很多耶可以转到带权上orz

http://acm.hdu.edu.cn/showproblem.php?pid=3047
Zjnu Stadium HDU - 3047 带权并查集板子题

板子

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200000+10;
////const int INF = 0x3f3f3f3f;
const int gxs = 3;
int n,m;
int pre[maxn],rnk[maxn];

void init() {
    for(int i=0; i<maxn; i++) pre[i]=i,rnk[i]=0;
}
//查找
int finds(int x){
    if(x==pre[x]) return x;
    int t=pre[x];
    pre[x]=finds(pre[x]);
    rnk[x]+=rnk[t];
    return pre[x];
}

//新建关系
void unions(int x,int y,int s) {
    int fx=finds(x),fy=finds(y);
    if (fx!=fy) {
        pre[fy]=fx;
        rnk[fy]=rnk[x]-rnk[y]+s;//+mod;
    //    rnk[fy]%=mod;
    }
}

int main() {
    int b,a,k;
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        init();
        int ans=0;
        for(int i=0;i<m;i++){
            cin>>a>>b>>k;
            if(finds(a)==finds(b)){
                if(rnk[a]+k!=rnk[b]) ans++;
            }else{
                unions(a,b,k);
            }
        }
        cout<<ans<<endl;
    } 
    return 0;
}

之后2题只是在带权并查集上 加了mod
就比如食物链 a吃b b吃c c吃a 一样 0 表示同类 1 表示x吃y 2表示y吃x
他们关系成环 所以知道 a b距离1 b c 距离又是 1 很显然 a c距离是2 这样 就是 c吃a 每次分析相对位置就好

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200000+10;
////const int INF = 0x3f3f3f3f;
//const long long mod = 1e9+7;
const int gxs = 3;
int n,m;
const int mod=3;

int pre[maxn],rnk[maxn];
//查找 

void init(){
    for(int i=0;i<maxn;i++) pre[i]=i,rnk[i]=0;
}
int finds(int x) 
{
    if(x==pre[x]) return x;
    else 
    {
        int root=finds(pre[x]);     // 找到根节点
        rnk[x]+=rnk[pre[x]];       // 权值合并，更新
        rnk[x]%=mod;
        return pre[x]=root;        // 压缩路径
    }
}

//新建关系
void unions(int x,int y,int m){
    int a=finds(x),b=finds(y);
    if(a!=b){
        pre[b]=a;
        rnk[b]=rnk[x]+m-rnk[y];
        rnk[b]+=gxs;
        rnk[b]%=gxs;
    }
} 

int main() {
    int b,a,k;
    ios::sync_with_stdio(false);
    cin>>n>>m;
        init();
        int ans=0;
        for(int i=0;i<m;i++){
            cin>>k>>a>>b;
            if((k==2&&a==b)||a>n||b>n||a<=0||b<=0) {
                ans++;
            }
            else if(k==1){
                if(finds(a)==finds(b)&&(rnk[a]!=rnk[b])) ans++;
                else  unions(a,b,0);
            }
            else if(k==2){
                if(finds(a)==finds(b)&&(rnk[a])!=(rnk[b]+2)%mod) ans++;
                else  unions(a,b,1);
            }
        }
        cout<<ans<<endl;

    return 0;
}

排序是必须的，我们要尽可能让危害大的罪犯在两个监狱里。
那么，再结合敌人的敌人和自己在一个监狱的规律合并。
当查找时发现其中两个罪犯不可避免地碰撞到一起时，只能将其输出并结束。
带权 mod取2；
wa 第一个点 就是没有冲突时输出 0 orz

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200000+10;
////const int INF = 0x3f3f3f3f;
const int gxs = 2;
const int mod=2;
int n,m;
int pre[maxn],rnk[maxn];

void init() {
    for(int i=0; i<maxn; i++) pre[i]=i,rnk[i]=0;
}
//查找
int finds(int x){
    if(x==pre[x]) return x;
    int t=pre[x];
    pre[x]=finds(pre[x]);
    rnk[x]+=rnk[t];
    rnk[x]%=gxs;
    return pre[x];
}

//新建关系
void unions(int x,int y,int s) {
    int fx=finds(x),fy=finds(y);
    if (fx!=fy) {
        pre[fy]=fx;
        rnk[fy]=rnk[x]-rnk[y]+s+gxs;
        rnk[fy]%=mod;
    }
}

struct node{
    int a,b;
    ll val;
    bool operator < (const node &a)const{
        return a.val<val;
    }
};

vector<node> que;

int main() {
    cin>>n>>m;
    int a,b;
    ll v;
    for(int i=0;i<m;i++){
        cin>>a>>b>>v;
        que.push_back(node{a,b,v});
    }
    sort(que.begin(),que.end());
    init();
//    ll ans=que[m-1].val;
    for(int i=0;i<m;i++){
        a=que[i].a;
        b=que[i].b;
        v=que[i].val;
        if(finds(a)==finds(b)){
            if(rnk[a]==rnk[b]){
                cout<<v<<endl;
                return 0;
            }
        }else{
            unions(a,b,1);
        }
    }
    cout<<0<<endl;
    return 0;
}

接下来二分图解法 二分枚举最大边 看看能不能切二部份

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=20000+10;
////const int INF = 0x3f3f3f3f;
const int gxs = 2;
const int mod=2;
int n,m;

struct node {
    int to;
    ll val;
};

vector<node> G[maxn];
int col[maxn];

void add_edge(int a,int b,ll v) {
    G[a].push_back(node {b,v});
    G[b].push_back(node {a,v});
}
int flag;
bool ok(ll mid) {
    queue <int> q;
    for(int i=1; i<=n; i++)
        if(!col[i]) {
            q.push(i);
            col[i]=1;
            while(!q.empty()) {
                int x=q.front();
                q.pop();
                for(int i=0; i<G[x].size(); i++)
                    if(G[x][i].val>=mid) {// 跟上面一样 不能二分图了 2人一个集合里面 出现的最小冲突 就是mid
                        if(!col[G[x][i].to]) {
                            q.push(G[x][i].to);
                            if(col[x]==1) col[G[x][i].to]=2;
                            else col[G[x][i].to]=1;
                        } 
                        if(col[G[x][i].to]==col[x])
                            return false;
                    }
            }
        }
    return true;
}

int main() {
    cin>>n>>m;
    int a,b;
    ll v;
    ll l,r;
    for(int i=0; i<m; i++) {
        cin>>a>>b>>v;
        add_edge(a,b,v);
        r=max(r,v);
    }
    r++;
    l=0;
    ll ans=r-1;
    while(r-l>1) {
        ll mid=(l+r)>>1;
    //    flag=0;
        memset(col,0,(n+5)*sizeof(int));
        if(ok(mid)) {
            r=mid;
        } else l=mid;
    }
    cout<<l;
    return 0;
}