[BZOJ 2654] tree · 二分答案

根據MST算法的性質，每次選權值最小的邊，是以我們可以給白邊加上或減去一個權值k，令白邊被少選或者多選，二分k即可。

PS：機房裡大神突然讨論起一個好像很有道理但實際上并沒用什麼卵用的問題：如果當某一個權值有很多條白邊和黑邊，如果加上一個k的時候隻選到了need-1條邊，而加上k+1的時候會選到need+1條邊，怎麼辦？   一開始好像覺得這個問題很神，但是突然發現很扯有沒有啊！這個時候白邊和黑邊的權值都相等了，反正又不要輸出方案，考慮這個有個毛線用啊！

#include <stdio.h>
#include <string.h>
#include <algorithm> 
using namespace std;

const int N=100005;
struct arr{
	int x,y,c,z;
}data[N],a[N];
int n,m,ans,cnt,k,l,r,mid,fa[N],ret;

bool cmp(const arr a , const arr b){
	return a.z==b.z ? a.c<b.c : a.z<b.z;
}

int get(int x){
	if (fa[x]==x) return x;
	fa[x]=get(fa[x]);
	return fa[x];
}

void kruskal(){
	cnt=ans=0;
	int p=0;
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;p<n-1;i++){
		int fx=get(data[i].x),fy=get(data[i].y);
		if (fx!=fy){
			fa[fx]=fy;
			p++;ans+=data[i].z;
			if (!data[i].c) cnt++;
		}
	}
}

int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].c);
		a[i].x++;a[i].y++;
	}
	l=-101;r=101;
	while (l<=r) {
		mid=(l+r)>>1;
		memcpy(data,a,sizeof data);
		for (int i=1;i<=m;i++)
			if (!data[i].c) data[i].z-=mid;
		sort(data+1,data+m+1,cmp);
		kruskal();
		if (cnt<k) l=mid+1;
			else {r=mid-1;ret=ans+k*mid;}
	}
	printf("%d\n",ret);
	return 0; 
}