还没理解透彻, 边记着.
在张主席和冯佬的解答下, 应该理解透彻了吧…
求贡献和的最值, 但是限制了某个东西必须选恰好$k$个.
没有个数限制很容易做.
把有限制条件的东西带上一个附加一个假想贡献. 也就是说, 选了一个这个东西, 就往我们计算的答案总贡献里加上 $\delta$.
$\delta$ 越大, 可能选得的这个东西数量越多/越少.
这样, 我们可以二分 $\delta$, 使得恰好选 $k$ 个, 然后贡献里减去我们假想出来的那一部分.
洛谷
给你一个无向带权连通图, 每条边是黑色或白色. 让你求一棵最小权的恰好有 $need$ 条白色边的生成树.
边权为整数.题目保证有解.
$n \le 5 \cdot 10^4, m \le 10^5, 1 \le w \le 100$
先这么想:
我们对这棵树进行kruskal, 需要对边按照权值排序. 然而, 仅仅按照权值排序做出来的MST并不是恰好有 $need$ 条白边的生成树. 所以要"打乱排序规则", 让白边更靠前或靠后一点.
如何修改白边的位置呢?
我们还发现, 白边也是取越小的权值的边. 所以, 尝试修改所有白边的权值, 全部加上 $\delta$, 然后做一下MST.
可以发现, 随着 $\delta$ 的增大, 取得的白边数量 $w$ 会减小(非严格), 也就是具有单调性. 所以二分 $\delta$ 就可以解决了.
最后的答案是我们求的MST结果要减去 $w(need) \cdot \delta$
注意到边权是整数, $\delta$ 也应该取整数, 是整数上的二分. 这样就会出现一个问题, $\delta_0$ 时, $w > need$; $\delta_0 + 1$ 时, $w < need$, 没有点能恰好让 $w$ 取到 $need$.
想想为什么会出现这样的情况.
当我们修改一条白边的边权为 $k$ 时, 恰巧有几个黑边的边权也为 $k$, 假如我们的排序是边权相等时优先取白边. 那么这时$w$相对上一个求的$w_{last}$变化就大于1了. 这就是造成不能恰好取到 $need$ 的原因. 权值相等优先取黑边也有同样的问题.
解决方案是: 权值相等优先取白边. 这样二分每个 $\delta$ 对应的$w$中, 取第一个大于等于 $need$ 的 $w_1$, 设最后一个小于 $need$ 的为 $w_0$; 如果 $w_1 > need$ 并且 $w_0 < need$, 证明存在权值相等的黑边和白边. 此时, 我们只需要将若干条白边换成黑边即可, 这样MST值不变, 但我们在最后算答案的时候要减去的是 $need \cdot \delta$ (而不是 $w \cdot \delta$).
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
const int MAXN = 1e5+10;
const int WHITE = 0;
const int BLACK = 1;
struct Edge {
int u, v, w;
bool operator < (const Edge &E) {
return w < E.w;
}
} edges[2][MAXN];
int mm[2];
int n, m, need, ans;
int fa[MAXN];
void init() {
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y) {
fa[find(x)] = find(y);
}
int check(int delta, int &res) {
init();
res = 0;
int w = 0, i = 1, j = 1;
while (i <= mm[WHITE] && j <= mm[BLACK]) {
if (edges[WHITE][i].w + delta <= edges[BLACK][j].w) {
if (find(edges[WHITE][i].u) != find(edges[WHITE][i].v)) {
w++, res += edges[WHITE][i].w + delta;
uni(edges[WHITE][i].u, edges[WHITE][i].v);
}
i++;
}
else {
if (find(edges[BLACK][j].u) != find(edges[BLACK][j].v)) {
res += edges[BLACK][j].w;
uni(edges[BLACK][j].u, edges[BLACK][j].v);
}
j++;
}
}
while (i <= mm[WHITE]) {
if (find(edges[WHITE][i].u) != find(edges[WHITE][i].v)) {
w++, res += edges[WHITE][i].w + delta;
uni(edges[WHITE][i].u, edges[WHITE][i].v);
}
i++;
}
while (j <= mm[BLACK]) {
if (find(edges[BLACK][j].u) != find(edges[BLACK][j].v)) {
res += edges[BLACK][j].w;
uni(edges[BLACK][j].u, edges[BLACK][j].v);
}
j++;
}
return w;
}
int main() {
scanf("%d%d%d", &n, &m, &need);
for (int i = 1; i <= m; i++) {
int u, v, w, c;
scanf("%d%d%d%d", &u, &v, &w, &c);
u++, v++;
edges[c][++mm[c]] = Edge{u, v, w};
}
sort(edges[WHITE]+1, edges[WHITE]+mm[WHITE]+1);
sort(edges[BLACK]+1, edges[BLACK]+mm[BLACK]+1);
int l = -101, r = 101;
while (l <= r) {
int mid = (l+r) >> 1, sum = 0, w = 0;
if ((w = check(mid, sum)) >= need) {
ans = sum - need * mid;
l = mid + 1;
}
else
r = mid - 1;
}
printf("%d\n", ans);
return 0;
}
|
一种套路, 题目符合
- 求贡献和的最值
- 限制了某个东西必须选恰好$k$个.
- 没有个数限制很容易做.
- 把有限制条件的东西带上一个附加贡献$\delta$, 且$\delta$越大, 可能选得的这个东西数量越多/越少.
就可以直接用.
然后要注意一下选择条件, 选这个东西和不选贡献相等时, 选上, 二分到大于等于$k$的第一个数的答案, 减去 $k\delta$ 即可.