2
24
2016
0

[BZOJ2654] tree

怎么说呢……神奇的二分

每次把白色边加上一个二分的权值,再做最小生成树

如果大于need条边就说明加上的权值太小了需要增大

反之亦然(因为题目保证有解,所以必然会存在这样的一个权值)

注意排序时权值相等时白色边放在前面

#include<cstdio>
#include<algorithm>
using namespace std;

int V,E,need,f[100005],test=0,ne=0;

struct Edge{
int a,b,v,co;
friend bool operator<(Edge a,Edge b){
return a.v==b.v?a.co<b.co:a.v<b.v;
}
}e[100005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa<sb)f[sb]=sa;
else f[sa]=sb;
}

int Check(int ans){
test=ne=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++){
	if(!e[i].co)e[i].v+=ans;
}
sort(e+1,e+E+1);
for(int i=1;i<=E;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		test+=e[i].v;
		if(!e[i].co)ne++;
	}
}
for(int i=1;i<=E;i++){
	if(!e[i].co)e[i].v-=ans;
}
return ne>=need;
}

int main(){
freopen("2654.in","r",stdin);
freopen("2654.out","w",stdout);
scanf("%d %d %d",&V,&E,&need);
for(int i=1;i<=E;i++){
	scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].v,&e[i].co);
	e[i].a++;
	e[i].b++;
}
int l=-105,r=105,ans;
while(l<=r){
	int mid=l+r>>1;
	if(Check(mid)){ans=test-need*mid;l=mid+1;}
	else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 559

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com