codeforces 687D Dividing Kingdom II 带权并查集（dsu）

题意：给你m条边，每条边有一个权值，每次询问只保留编号l到r的边，让你把这个图分成两部分

一个方案的耗费是当前符合条件的边的最大权值（符合条件的边指两段点都在一个部分），问你如何分，可以让耗费最小

分析：把当前l到r的边进行排序，从大到小，从大的开始不断加边，判断当前能否形成二分图，如果能形成二分图，继续加边

如果不能形成二分图，那当前边的权值就是最小耗费(是不是很眼熟)

思路很清晰，现在我们要解决的是如何判断可以形成二分图，有两种，一个是2染色当前图（肯定超时）

所以只剩一种方法，带权并查集

带权并查集三步走

1：设计权值数组relation[i],代表i节点和它的根的关系，0代表属于一个部分，1代表不属于一个部分

2：路径压缩，relation[i]=relation[i]^relation[fa[i]]，递归得到和根的关系

3：合并根节点,relation[i]=relation[u]^relation[v]^1;

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <stack>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=5e5+;

int fa[N],relation[N];

struct Edge{

  int u,v,w,id;

  bool operator<(const Edge &rhs)const{

      return w>rhs.w;

  }

}p[N];

int find(int x){

  if(x==fa[x])return x;

  int fx=find(fa[x]);

  relation[x]^=relation[fa[x]];

  return fa[x]=fx;

}

bool Union(int u,int v){

  int fx=find(u),fy=find(v);

  if(fx==fy){

    if(relation[u]==relation[v])

      return false;

    return true;

  }

  fa[fx]=fy;

  relation[fx]=relation[u]^relation[v]^;

  return true;

}

int main(){

    int n,m,q;

    scanf("%d%d%d",&n,&m,&q);

    for(int i=;i<=m;++i){

      scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);

      p[i].id=i;

    }

    sort(p+,p++m);

    while(q--){

      int l,r,ret=-;

      scanf("%d%d",&l,&r);

      for(int i=;i<=n;++i)fa[i]=i,relation[i]=;

      for(int i=;i<=m;++i){

        if(p[i].id<l||p[i].id>r)continue;

        if(!Union(p[i].u,p[i].v)){

          ret=p[i].w;break;}

      }

      printf("%d\n",ret);

    }

    return ;

}

巴特西

codeforces 687D Dividing Kingdom II 带权并查集（dsu）

最新文章

热门文章