翻车笔记_ BZOJ2654 tree [最小生成树, kruskal, 清奇脑回路]

经典算法改一改, 就不会做了…

懵逼的 题目

GG

扯淡的 题解

和昊哥yy了半天, 无果, 于是抄题解

感觉思路挺有意思的…

  • 二分一个值$k$, 然后把所有的白边的边权都加上$k$
  • kuskal, 记录生成树中白边的条数$re$
    • $re > need$: 把$k$变大
    • $re < need$: 把$k$变小
    • $re = need$: 这时的生成树权值就是答案

因为给白边加的都是一个数, 所以白边的相对大小没变, 选出来的还是最小的那些白边, 所以答案是正确的…

沙茶的 代码

实现的时候注意可能白边黑边的权值一样, 所以实际写起来是下面这样…

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
87
88
89
90
91
92
93
94
95
96
/**************************************************************
Problem: 2654
User: Cansult
Language: C++
Result: Accepted
Time:7116 ms
Memory:4812 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXM (100000 + 5)
#define INF (0x7fffffff)
#define int long long
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct edg
{
int from, to, cost, ki;
}b[MAXM];
int fa[MAXN], n, m, need, nw;
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); }
bool cmp(edg x, edg y)
{
if (x.cost != y.cost)
return x.cost < y.cost;
else
return x.ki < y.ki;
}
pii kruskal()
{
for (int i = 1; i <= n; i++)
fa[i] = i;
sort(b + 1, b + m + 1, cmp);
int cntb = 0;
pii re = mkp(0, 0);
for (int i = 1; i <= m; i++)
if (find(b[i].from) != find(b[i].to))
{
if (re.first >= need && !b[i].ki)
{
re.first = need + 1;
continue;
}
++cntb;
re.first += 1 - b[i].ki;
re.second += b[i].cost;
uni(b[i].from, b[i].to);
if (cntb == n - 1)
break;
}
return re;
}
int ef()
{
int le = -200, ri = 200, last = 0, re = INF;
while (le < ri)
{
int mi = (le + ri) >> 1;
for (int i = 1; i <= m; i++)
if (!b[i].ki)
b[i].cost += mi - last;
pii dq = kruskal();
if (dq.first >= need)
{
re = min(re, dq.second - nw * mi);
le = mi + 1;
}
else
ri = mi;
last = mi;
}
return re;
}
main()
{
scanf("%lld%lld%lld", &n, &m, &need);
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%lld%lld%lld%lld", &srx, &sry, &b[i].cost, &b[i].ki);
++srx, ++sry;
b[i].from = srx, b[i].to = sry;
if (!b[i].ki)
++nw;
}
printf("%lld\n", ef());
return 0;
}

By 沙茶 Cansult