@ysner
2018-09-26T18:56:26.000000Z
字数 1348
阅读 1943
二分
生成树
给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
好像有个套路:
对于有个数要求的某种边,可以改变它们的权值,以改变它们加入最小生成树的顺序(包括移出最小生成树)。
改变量可以二分。因为改变量(包括符号)越大,加入的边就越少。
细节:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define db double
#define eps 1e-5
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,m,k,f[N];
ll ans;
bool use[N];
struct dat{int u,v,w,t;bool operator < (const dat &o) const {return (w<o.w)||(w==o.w&&t<o.t);}}a[N<<1],b[N<<1];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il int check(re int x)
{
re ll tag=0,tot=0;ans=0;
fp(i,1,n) f[i]=i;
fp(i,1,m)
{
a[i]=b[i];
if(!a[i].t) a[i].w+=x;
}
sort(a+1,a+1+m);
fp(i,1,m)
{
re int u=find(a[i].u),v=find(a[i].v);
if(u^v) f[v]=u,ans+=a[i].w,tag+=(a[i].t==0),++tot;
}
return tag>=k;
}
int main()
{
n=gi();m=gi();k=gi();
fp(i,1,m)
{
a[i].u=gi()+1,a[i].v=gi()+1,a[i].w=gi();a[i].t=gi();
b[i]=a[i];
}
re int l=-105,r=105,gu=0;
while(l<=r)
{
re db mid=l+r>>1;
if(check(mid)) gu=mid,l=mid+1;
else r=mid-1;
}
check(gu);
printf("%lld\n",ans-gu*k);
return 0;
}