I-图的分割(二分+并查集)

图的分割

题目大意：

给你n个点，m条边的图，没有重环和自环，所有的点都联通

可以通过删除几条边使得整个图变成两个联通子图

求删除的边中最大边权的最小值

解题思路：

看到“最大边权的最小值”就晓得是经典的二分题目了，所以整体的代码就是二分，现在考虑check()怎么写

（当然边需要经过排序后再去二分）

因为是通过删除几条边而使整个图一分为二，换句话说就是删除边之后的图有两个点集合，那么就可以想到用并查集来维护集合，每次check()时重置集合，将不删除的边连起来，看整个图中有几个集合

代码实现：

#include<bits/stdc++.h>

using namespace std;

// # define int long long

# define endl "\n"

const int N = 1e6+10;

int f[N];

int n,m;

int cnt[N];

struct node{

    int a,b,v;

}a[N];

int find(int x){

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

    return f[x] = find(f[x]);

}

bool check(int mid){

    for(int i = 1;i <= n;++i) f[i] = i,cnt[i] = 1;

    for(int i = mid+1;i<=m;++i)//删除前mid个边，将后面的边连起来

    {

        int x = find(a[i].a);

        int y = find(a[i].b);

        if(x != y){

            if(cnt[x]>cnt[y]) swap(x,y);//启发式合并

            f[x] = y;

        }

    }

    int cnt = 0;

    for(int i = 1;i <= n;++i)//查看图中有几个集合

    {

        if(f[i] == i) cnt++;

    }

    return cnt>=2;

}

void solve(){

    cin>>n>>m;

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

        cin>>a[i].a>>a[i].b>>a[i].v;

    }

    sort(a+1,a+1+m,[&](node a,node b)->bool{

        return a.v<b.v;

    });//对边按边权排序

    int l = 1,r = m;

    int ans = 0;

    while(l<=r){

       int mid = l+r>>1;

       if(check(mid)){

           r = mid-1;

           ans = mid;

       }

       else l = mid+1;

   }

    cout<<a[ans].v<<endl;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int tt;

    tt = 1;

//     cin>>tt;

    while(tt--) solve();

    return 0;

}

巴特西

I-图的分割(二分+并查集)

图的分割

题目大意：

解题思路：

代码实现：

最新文章

热门文章