Description

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

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

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

Sample Input

1
2
3
2 2 1
0 1 1 1
0 1 2 0

图示：

Sample Output

1
2

分析

这道题要用到二分法，对 $Kruskal$ 算法进行变形，首先我们在对边集排序时，要让值相等的情况下白色边在前（为了选边做准备），然后为了影响 $Kruskal$ 的选边过程，对所有的白色边加上一个权值，这个权值可正可负，这是因为将编边集数组排序时：

  1. 附加权为正时，表示当前的白色边过多，我们让权值较大的白色边再大一点，就可以被$Kruskal$ 算法排除在最小生成树外面，达到少选的目的
  2. 附加权为负时，表示当前的白色边过少，让所有白色边权值变小、前移就可以多选白色边

发现这样做实际上只影响了白色边和黑色边的顺序，没有影响白色边之间的相对顺序，因此 $Kruskal$ 选出来的边就还会是满足需要的条件下的最小生成树

要二分的就是附加权的权值，二分直到最小生成树中刚好有 $need$ 条白色边，每次让 $Kruskal$ 返回一个值 $cnt​$ ，表示选了多少条白色边，然后：

$cnt\geq need$ $cnt<need$
说明白色边较多，需要调小权值 说明白色变较少，需要调大权值

二分完，此时的目标权值和为 $Sum-need\times add$，$add$ 是二分的权值，每次二分完后记得恢复原来的边权

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxV 50001
#define maxE 100001
using namespace std;
struct node{
	int u,v,val;
	int c;
	bool operator <(const node &obj)const{
		if(val==obj.val) return c<obj.c;
		else return val<obj.val;
	}
}g[maxE]; int f[maxV],V,E,need;
inline int Sfind(int x){
	if(f[x]==x) return x;
	else return f[x]=Sfind(f[x]);
}
#define Sunion(u1,u2) (f[Sfind(u1)]=Sfind(u2))
pair<int,int> kruskal(){
	sort(g+1,g+E+1);
	int cnt=0,ans=0;
	for(int i=0;i<=V;i++) f[i]=i;
	for(int i=1;i<=E;i++){
		if(Sfind(g[i].u)!=Sfind(g[i].v)){
			Sunion(g[i].u,g[i].v);
			ans+=g[i].val;
			if(g[i].c==0) cnt++;
		}
	}
	return make_pair(cnt,ans);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	cin>>V>>E>>need; int l,r=0;
	for(int i=1;i<=E;i++){
		cin>>g[i].u>>g[i].v>>g[i].val>>g[i].c;
		g[i].u++; g[i].v++;
		r=max(r,g[i].val);
	}
	l=r*-1; int mid; pair<int,int> res;
	int ret=1;
	while(l<=r){
		mid=(l+r)>>1;
		for(int i=1;i<=E;i++)
			if(g[i].c==0) g[i].val+=mid;
		res=kruskal();
		if(res.first>=need)
			ret=res.second-need*mid,
			l=mid+1;
		else r=mid-1;
		for(int i=1;i<=E;i++)
			if(g[i].c==0) g[i].val-=mid;
	}
	cout<<ret;
	return 0;
}