【BZOJ 1196】[HNOI2006]公路修建问题

在这里输入题意

【题解】

二分最后选的边中的最大值是多少。
mid

则所有边权小于等于mid的边都可以用了。

那么我们要怎么选择呢?

->优先选择一级的道路。

因为它比较贵一点。

那么找到所有一级道路小于等于mid的路径。

(既然可以连,为什么不连?就算连的是二级道路,它对联通性的贡献也是一样的

(而且二级道路更便宜,所以肯定也可以连

(所以可以这样贪心地连,且不会影响到最后答案

把它们都加进去。

->按照克鲁斯卡尔算法的并查集的方法连(如果已经有链接两个连通块的了就不连这条边

然后看看能不能凑够k条边

如果可以的话。

那么就继续凑2级的道路。

直到凑够n-1条边构成生成树为止。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int M = 2e4;

const int N = 1e4;

struct abc{

    int  x,y,c1,c2;

}a[M+10];

int n,k,m,f[N+10];

int ff(int x){

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

    else return f[x] = ff(f[x]);

}

bool ok(int bound){

    rep1(i,1,n) f[i] = i;

    int cnt = 0;

    rep1(i,1,m){

        if (a[i].c1>bound) continue;

        int x = ff(a[i].x),y = ff(a[i].y);

        if (x!=y){

            f[x] = y;

            cnt++;

        }

    }

    if (cnt<k) return false;

    rep1(i,1,m){

        if (a[i].c2>bound) continue;

        int x = ff(a[i].x),y = ff(a[i].y);

        if (x!=y){

            f[x] = y;

            cnt++;

        }

    }

    if (cnt<n-1) return false;

    return true;

}

int main(){

    #ifdef LOCAL_DEFINE

        freopen("rush_in.txt", "r", stdin);

    #endif

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

    rep1(i,1,m){

        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].c1,&a[i].c2);

    }

    int l = 1,r = 3e4,temp = -1;

    while (l <= r){

        int mid = (l+r)>>1;

        if (ok(mid  )){

            temp = mid;

            r = mid-1;

        }else l = mid+1;

    }

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

    return 0;

}

巴特西

【BZOJ 1196】[HNOI2006]公路修建问题

最新文章

热门文章