题解：SP11579 COMPANYS - Two Famous Companies

思路

题目大意

给你一个带权无向图，每条边非白即黑，现在要构造一个生成树使得恰有 $K$ 条白色的边，使权值和最小。

这道题目看上去向一个最小生成树的模版，但其实并不是。

因为在这个最小生成树有 $2$ 种边，白边和黑边。因为黑边的加入，导致我们的 kruskal 会产生错误的答案。

比如说，黑边的所有权值都比白边小，那么一味的套模版最终可能 kruskal 跑出来的不是正确的结果。

怎么办呢？我们可以进行二分答案，二分的东西是一个增添值。如果白边权值比黑边小，那么就加上它，如果大了，就减掉它。

但是要在最后复原。复原的这个值为 $k\times mid$，因为我们要选取 $k$ 个白边，所以要减去 $k$ 个 $mid$。

采取了二分答案，接下来就是二分的范围，因为边的权值在 $-100\le c\le 100$，所以二分的范围就是 $-100\sim 100$。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<queue>
#define int long long

using namespace std;

const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;

int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') f = -1;
		ch = getchar();
	} 
	while (isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
} 

struct node {
	int u, v, w, x;
}e[100005];

int n, m, k, t;
int ans, sum, whitesum, cntsum;
int f[50004], s[50004];

int find(int x) {
	if (x == f[x]) return x;
	return f[x] = find(f[x]);
}

void conn(int p, int q) {
	int rootp = find(p);
	int rootq = find(q);
	if (s[rootp] > s[rootq]) 
		f[rootq] = rootp, s[rootp] += s[rootq];
	else
		f[rootp] = rootq, s[rootq] += s[rootp];
}

bool isconn(int p, int q) {
	return find(p) == find(q);
}

void clean() {
	cntsum = whitesum = sum = 0;
	for (int i = 1; i <= n; i++) 
		f[i] = i, s[i] = 1;
}

bool cmp(node x, node y) {
	if (x.w != y.w) return x.w < y.w;
	return x.x < y.x;
}

signed main() {
	while (scanf("%lld%lld%lld", &n, &m, &k) == 3) {
		t++;
		for (int i = 1; i <= m; i++) {
			e[i].u = read(), e[i].v = read(), e[i].w = read();
			e[i].x = read();
			e[i].u++, e[i].v++;
		}
		int l = -100, r = 100, mid;
		while (l <= r) {
			mid = (l + r) >> 1;
			for (int i = 1; i <= m; i++)
				if (e[i].x == 0) e[i].w += mid;
			clean();
			sort(e + 1, e + m + 1, cmp);
			for (int i = 1; i <= m; i++) {
				if (!isconn(e[i].u, e[i].v)) {
					conn(e[i].u, e[i].v);
					cntsum++; 
					if (e[i].x == 0) whitesum++;
					sum += e[i].w;
					if (cntsum >= n - 1) break;
				}
			}
			for (int i = 1; i <= m; i++) 
				if (e[i].x == 0) e[i].w -= mid;
			if (k > whitesum) r = mid - 1;
			else l = mid + 1, ans = sum - k * mid;
		}
		printf("Case %lld: %lld\n", t, ans);
	}
	return 0;
}