hdu4253 Two Famous Companies --- 二分+MST

给n个点。m条边的图。每条边要么属于a公司，要么属于b公司。要求一颗最小生成树，条件是当中属于a公司的边数为k。

这题做法非常巧妙。

要求最小生成树，但有一定限制，搜索、贪心显然都不正确。

要是能找到一种合理的控制方法，使得求MST的过程中能够控制a公司边的数量。那样问题就攻克了。

所以我们能够人为给a公司的边加上一定的权值。使得当中一些边不得不退出MST的选择范围内。

假设此时求的mst里a公司的边数>k，那么就要添加权值。边数<k时，权值为负。

所以，通过二分边权值，能够使得求得mst里所含a公司的边数逐渐逼近k，此时记录答案，由于一定有解，所以终于一定是所求答案。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxm=100010;

const int maxn=50010;

struct node

{

    int u,v,w,ty;

}e[maxm];

int r[maxn],n,m,k,ret,telecom;

bool cmpw(node a,node b)

{

    if(a.w!=b.w) return a.w<b.w;

    return a.ty<b.ty;

}

int root(int a)

{

    if(r[a]==-1) return a;

    return r[a]=root(r[a]);

}

bool kru(int x)

{

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

        if(e[i].ty==0) e[i].w+=x;

    sort(e,e+m,cmpw);

    memset(r,-1,sizeof r);

    int edge=0;telecom=n-1;ret=0;

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

    {

        int ra=root(e[i].u);

        int rb=root(e[i].v);

        if(ra!=rb)

        {

            r[ra]=rb;

            ret+=e[i].w;

            telecom-=e[i].ty;

            if(++edge==n-1) break;

        }

    }

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

        if(e[i].ty==0) e[i].w-=x;

    return telecom>=k;

}

int main()

{

    int cas=1;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

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

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

        int l=-100,r=100,mid,ans=0x3f3f3f3f;

        while(l<=r)

        {

            mid=(l+r)/2;

            if(kru(mid)) l=mid+1,ans=ret-mid*k;

            else r=mid-1;

        }

        printf("Case %d: %d\n",cas++,ans);

    }

    return 0;

}