洛谷P2619 [国家集训队]Tree I

can can need?一道很好的二分题目,阐释了进阶的二分思想的运用,扩展了原本二分局限的思想.
原本我一直认为二分都是一些满足单调性的东西,虽然这个题也确实是,但是它的单调性其实是比较模糊的。
求最小生成树,但是要求白边的边数一定是$need$情况下的.
考虑下二分出这个$cost$,接下来是检验能否在指定的$cost$内,是否能找到$need条白边$,$n-1-need$条黑边的生成树.
然后我就又又又没有思路,以上仍然是胡编乱造的,去看题解了.
原来我理解错题目的意思了,意思
首先对原始的边进行Kruskal，随便跑出一个MST,假设有$x$条白边.
接下来对$x$讨论,如果$x>need$,证明白边的边权是比较小的,我们需要把一些白边替换成黑边,如何替换呢,我们考虑整体把原本白色的边的边权稍加修改,如果$x>=need$,说明白边比较多,考虑把它扔到后边$把边权整体加上y$.反之,如果$x<need$,那么就要减去$y$.
显然此处的$y$的加减过于抽象,不如直接让$y$是一个变量算了.二分这个$y$,每次二分到$x>=need$情况,我们需要更新一次答案.

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 1000010;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
struct Edge{
	int u,v,w,c;
}edge[maxn];
bool cmp(Edge a,Edge b){
	if(a.w==b.w) return a.c<b.c;
	return a.w<b.w;
}
int n,m,need;
int f[maxn];
int find(int k){
	return f[k]==k?k:f[k]=find(f[k]);
}
ll white = 0,sum = 0;
void Kruskal(){
	sort(edge+1,edge+1+m,cmp);
	for(int i=0;i<=n+5;i++) f[i] =i;
	int cnt = 0;
	for(int i=1;i<=m;i++){
		Edge e = edge[i];
		int f1 = find(e.u);int f2 = find(e.v);
		if(f1!=f2){
			f[f1] = f2;cnt++;
			if(e.c==0) white++;
			sum+=e.w;
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>need;
	for(int i=1;i<=m;i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w>>edge[i].c;
		edge[i].u++,edge[i].v++;
	}
	int L = -111,R = 111;ll ans = -1;
	while(L<=R){
		int mid = (L+R)/2;
		for(int i=1;i<=m;i++){
			if(edge[i].c==0) edge[i].w += mid;
		}
		white =  sum = 0;//记得清空
		Kruskal();
		if(white>=need){
			ans = sum - 1LL*mid *need;
			L = mid + 1;
		}
		else R = mid  - 1;
		for(int i=1;i<=m;i++){
			if(edge[i].c==0) edge[i].w -= mid;
		}
	}
	cout<<ans<<"\n";
}

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
63
64
65
66
67
68
69
70
71