【BZOJ2654】Tree（凸优化，最小生成树）

题面

BZOJ

洛谷

题解

这道题目是之前\(Apio\)的时候写的，忽然发现自己忘记发博客了。。。

这个万一就是一个凸优化，

给所有白边二分一个额外权值，并且给边权加上这个权值。

然后跑最小生成树，将限制问题转换为判定问题即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m,K;

struct Link{int u,v,w,col;}e[MAX];

bool cmp(Link a,Link b){if(a.w!=b.w)return a.w<b.w;else return a.col<b.col;}

int f[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int check(int mid,int opt)

{

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

        if(!e[i].col)e[i].w-=mid;

    sort(&e[1],&e[m+1],cmp);

    for(int i=0;i<n;++i)f[i]=i;

    int cnt=0,tot=0,sum=0;

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

    {

        int u=e[i].u,v=e[i].v;

        if(getf(u)==getf(v))continue;

        f[getf(u)]=getf(v);

        ++tot;sum+=e[i].w;

        if(!e[i].col)++cnt;

        //if(tot==n-1)break;

    }

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

        if(!e[i].col)e[i].w+=mid;

    if(!opt)return cnt;

    else return sum;

}

int main()

{

    n=read();m=read();K=read();

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

        e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].col=read();

    int l=-101,r=101,ans=1e9;

    while(l<=r)

    {

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

        int d=check(mid,0);

        if(d>=K)r=mid-1,ans=mid;

        else l=mid+1;

    }

    printf("%d\n",check(ans,1)+K*ans);

    return 0;

}