给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有 need 条白色边的生成树。题目保证有解
题解
二分 + 最小生成树
二分一个权值,将每条白边都加上这个权值,然后跑最小生成树,如果使用的白边少了,则说明权值加大了,反之则说明权值加少了
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5 + 10;
int n, m, need, f[maxd * 5], sum;
struct node {
int a, b, c, col, d;
bool operator<(const node& other) const {
if (d == other.d)
return col < other.col;
return d < other.d;
}
} e[maxd];
void init() {
for (int i = 0; i <= n; i++) f[i] = i;
sum = 0;
}
int gf(int x) {
if (f[x] == x)
return x;
return f[x] = gf(f[x]);
}
int solve(int x) {
init();
int ans = 0, cnt = 0;
for (int i = 1; i <= m; i++) e[i].d = e[i].c + (1 ^ e[i].col) * x;
sort(e + 1, e + 1 + m);
for (int i = 1; i <= m; i++) {
int a = gf(e[i].a), b = gf(e[i].b);
if (a == b)
continue;
ans += 1 ^ e[i].col;
f[a] = b;
sum += e[i].d;
cnt++;
if (cnt + 1 == n)
return ans;
}
return ans;
}
int main() {
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
scanf("%d %d %d", &n, &m, &need);
for (int i = 1; i <= m; i++) scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].c, &e[i].col);
int l = -100, r = 100, ans;
while (l <= r) {
int mid = (l + r) >> 1;
if (solve(mid) >= need) {
// printf("%d %d\n",sum,mid);
ans = sum - need * mid;
l = mid + 1;
} else
r = mid - 1;
}
printf("%d", ans);
return 0;
}