题解 P2619 【[国家集训队2]Tree I】
HDWR
2019-01-31 21:36:41
~~年轻人的第一道国家集训队题目~~
---
如果我们不做任何处理，直接跑MST（Minimum Spanning Tree，最小生成树），结果会有三种：
- 正好跑出 $\text{Need}$ 条白边
- 白边多了
- 白边少了
第一种情况自然是最好的
剩下两种情况如何解决？
---
引起白边少的原因：黑边的边权相对较小，程序贪心地选择了更多的黑边
引起白边多的原因：白边的边权相对较小，程序贪心地选择了更多的白边
那么如果我们给白边相应地减去/加上一些边权，不就可以达成目标了？
---
考虑二分答案。
我们二分一个 $add$ 表示我们当前要给白边加上 $add$ 来达成目标
边界分别是边权最小值（-100）和边权最大值（100）
由于题面保证有答案，所以直接输出 $ ans - add \times \text{Need} $
即可，其中 $ans$ 为（加上边权后）最小生成树的权值和
`Check(mid)` 怎么写？
---
我们将所有白边的边权加上$add$（即$mid$），跑一遍最小生成树，判断一下拿到的白色边数量是否大于等于要求的数量，如果是就更新一下左边界并记当前的$mid$为$tans$，否则就更新一下右边界
注意不要忘了把边权减回来
（不要在意 $tans$ 是什么意思）
---
刚才我们不是记录了一下$tans$吗，这个$tans$就相当于是一个正确的、能选出正好 $\text{Need}$ 条白边的 $add$ 值，再将所有白边的边权都加上这个 $tans$，跑一遍最小生成树即可
答案不要忘了减去加上的边权（也就是 $ \text{Need} \times tans $）
那么最后的答案就是 $ \text{Kruskal()} - \text{Need} \times tans $
# 代码实现
```cpp
#include <algorithm>
#include <iostream>
#include <cstdio>
#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define WHITE 0
#define BLACK 1
using std::cin;
using std::cout;
using std::endl;
using std::max;
const int MAXV = 50000 + 10;
const int MAXE = 100000 + 10;
const int MAXW = 100;
struct Edge {
int prev, next, weight, add;
bool color;
// 1 -> black, 0 -> white
Edge() { prev = next = weight = color = add = 0; }
bool operator < (const Edge &that) const {
if (weight == that.weight) return color < that.color;
return weight < that.weight;
}
} edge[MAXE << 1];
int V, E, Need, cnt, ans;
int U[MAXV << 1];
int Find(int x) {
if (U[x] == x) return U[x];
return U[x] = Find(U[x]);
}
bool Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return false;
U[x] = y;
return true;
}
int Kruskal() {
int whiteEdge = 0;
for (int i = 1; i <= V; ++i) U[i] = i;
std::sort(edge + 1, edge + 1 + E);
int tot = 0;
ans = 0;
for (int i = 1; i <= E; ++i) {
if (Union(edge[i].prev, edge[i].next))
ans += edge[i].weight, ++tot, whiteEdge += (edge[i].color == WHITE);
if (tot == V - 1) break;
}
return whiteEdge;
}
bool Check(int add) {
for (int i = 1; i <= E; ++i) {
if (edge[i].color == WHITE) edge[i].weight += add;
}
bool Ans = (Kruskal() >= Need);
for (int i = 1; i <= E; ++i) {
if (edge[i].color == WHITE) edge[i].weight -= add;
}
return Ans;
}
int main() {
IMPROVE_IO();
cin >> V >> E >> Need;
for (int i = 1; i <= E; ++i) {
cin >> edge[i].prev >> edge[i].next >> edge[i].weight >> edge[i].color;
++edge[i].prev;
++edge[i].next;
}
int l = -MAXW, r = MAXW;
int Run = 0;
while (l <= r) {
int mid = ((l + r) >> 1);
if (Check(mid)) {
l = mid + 1;
Run = mid;
} else {
r = mid - 1;
}
}
Check(Run);
cout << ans - Need * Run << endl;
return 0;
}
```