BZOJ2654: tree

题解:　　orz这个二分　首先我们来分析一下　边数与权值的关系　显然的随着白色边的权值增加会导致白色边的数量减少那么　我们可以通过二分找到恰好为need的白边的位置　　同同构造MST保证此时的边权和最小　出现的问题是你二分加的权值会出现白边和黑边相等情况　此时优先白边加入　排序的时候加一下限制即可

#include <bits/stdc++.h>
const int MAXN=5e4+10;
using namespace std;
int n,m,ned;
typedef struct node{
	int id,u,v,vul,key;
}node;
node d[MAXN<<1];
bool cmp(node aa,node bb){
	if(aa.key==bb.key)return aa.id<bb.id;
	return aa.key<bb.key;
}
int f[MAXN],key;
int find1(int x){
	if(f[x]==x)return x;
	else return f[x]=find1(f[x]);
}
bool check(int t){
	for(int i=1;i<=m;i++){
		if(d[i].id==0)d[i].key=d[i].vul+t;
		else d[i].key=d[i].vul;
	}
	sort(d+1,d+m+1,cmp);key=0;
	int cnt=0;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int t1=find1(d[i].u);int t2=find1(d[i].v);
		if(t1==t2)continue;
		f[t1]=t2;key+=d[i].key;
		if(!d[i].id)cnt++;
	}
	if(cnt>=ned)return 1;
	return 0;
}
int main(){
	scanf("%d%d%d",&n,&m,&ned);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)scanf("%d%d%d%d",&d[i].u,&d[i].v,&d[i].vul,&d[i].id),d[i].u++,d[i].v++;
	int l=-110,r=110,ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=key-ned*mid;
		else r=mid-1;
	}
	printf("%d
",ans);
}

2654: tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 3245 Solved: 1369
[Submit][Status][Discuss]

Description

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。

题目保证有解。

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24