题目
bzoj2654: tree
解析
kruscal在做最小生成树时先按权值排序，权值小的先被选到，我们可以通过控制白色边的边权来控制白色边的数量。 我们可以通过二分答案来给白边加某一个值 同时注意两点
不要忘记减去给白边加的值排序时白边优先
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, num, need, ans, tot, sum, cnt;
int fa[N], head[N], w[N];
struct node {
int u, v, w, col;
bool operator <(const node &oth) const {
return w == oth.w ? col < oth.col : w < oth.w;
}
} e[N], tmp[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int kruscal() {
cnt = 0, sum = 0, ans = 0;
for (int i = 1; i <= n; ++i) fa[i] = i;
sort(e + 1, e + 1 + m);
for (int i = 1; i <= m; ++i) {
int x = find(e[i].u), y = find(e[i].v);
if (x == y) continue;
fa[x] = y;
ans += e[i].w;
if (!e[i].col) sum++;
cnt++;
if (cnt == n - 1) break;
}
return sum;
}
bool check(int x) {
for (int i = 1; i <= m; ++i) {
e[i] = tmp[i];
if (!e[i].col) e[i].w += x;
}
return kruscal() >= need;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> need;
for (int i = 1, x, y, z, c; i <= m; ++i) {
cin >> x >> y >> z >> c;
e[i] = (node) {x + 1, y + 1, z, c};
tmp[i] = (node) {x + 1, y + 1, z, c};
}
int l = -1000, r = 1000;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, tot = ans - need * mid;
else r = mid - 1;
}
cout << tot;
return 0;
}
转载于:https://www.cnblogs.com/lykkk/p/11223011.html
相关资源：JAVA上百实例源码以及开源项目
