2654: tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 4829 Solved: 2093
[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
2

wqs它的作用就是题目给了一个选物品的限制条件，要求刚好选m个，让你最大化（最小化）权值，
然后其特点就是当选的物品越多的时候权值越大（越小）。

然后这类题目，我们就可以wqs二分啦，对于这道题，我们就是给我们白色的边，减去一个权值，使得白色边具有更高的优先级，然后统计答案时加上即可。

wqs的正确性可以用凸函数来计算。

注意不能直接选need条需要的最小白色边，因为白色边会影响到黑色边的选取。

还有统计答案时只需要加上need边的权值。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int f[N<<1],n,m,need,cnt,res,sum,num;
struct node{int u,v,w,col;}t[N];
int cmp(node a,node b){return a.w==b.w?a.col<b.col:a.w<b.w;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int kruskal(int mid){
	for(int i=1;i<=n;i++)	f[i]=i;
	for(int i=1;i<=m;i++)	if(!t[i].col)	t[i].w-=mid;
	sort(t+1,t+1+m,cmp);	int cnt=0; sum=num=0;
	for(int i=1;i<=m&&cnt<n-1;i++){
		int fa=find(t[i].u); int fb=find(t[i].v);
		if(fa!=fb){
			cnt++;	sum+=t[i].w;	f[fa]=fb;	num+=(!t[i].col);
		}
	}
	for(int i=1;i<=m;i++)	if(!t[i].col)	t[i].w+=mid;
	return num;
}
int wqs(){
	int l=-100,r=100;
	while(l<r){
		int mid=l+r>>1;
		if(kruskal(mid)>=need){
			res=sum+need*mid;	r=mid;
		}
		else	l=mid+1;
	}
	return res;
}
signed main(){
	cin>>n>>m>>need;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %d",&t[i].u,&t[i].v,&t[i].w,&t[i].col);
		t[i].u++; t[i].v++;
	}
	cout<<wqs()<<endl;
	return 0;
}