显然卡牌和药全用完最优，然后我们可以变成，构建一条欧拉路径，使得权值和最大，权值定义为，能把卡片效果用出来的边，即如果一张卡牌是 $x\to y$ ，而我们也确实让这张卡牌这么干了。
又可以注意到，我们可以把终点和起点连起来，变成欧拉回路，即我们添加一瓶能到初始状态的药，然后要求最终回到初始状态，这两个问题显然是等价的。
这样，每个点的总入度是知道的，现在问题在于，我们能保留多少张卡牌的效果。
一个显然的事情是：一个点有多少入度，我们就会保留等量的从大到小的以这个点为起始点的卡牌。
但有一个问题，这样不一定连通。
我们不妨统计选的边所贡献的入度和出度，显然一个点的出度小于等于这个点的总入度。
可以发现，这个选法有效当且仅当，将单向边当成双向边后，一个连通块的总入度和 $>$ 出度和。
思考一下什么时候等于，一个连通块的出度和等于入度和，入度 $\le$ 总入度，即总入度等于入度，所以这个连通块中所选择的边就是这个连通块所有的入边，即这个连通块没有块外的边连进来，同时因为入度等于总入读等于出度，所以这个连通块还是个欧拉图（单向边的情况下）。
现在要尝试花最小的代价使得其合法化，不妨猜一下，要么删除一条边，或者删除一条边，加入一条同起点的连向块外的边。
首先这一定是合法的，由于原来是欧拉图，所以一定强连通，所以连通块内仍连通，同时连通块的入度和等于总入度和等价于其中每个点都等于，而删除或者替换都会使原连通块不满足后者，所以新的连通块一定不满足。
问题是这为什么是最优的呢？
首先如果一开始没有孤立的团，那么显然是对的，假设有，假设有 $k$ 个，将点集分成 $k+1$ 部分，$X_1,X_2,…,X_{k+1}$ ，其中最后一个为补集。
尝试用局部最优的方法证明上面的那种选法就是上界，考虑每个集合中的点选出边，显然都会优先选最优的，但是任何方案都不可能包含 $X_{i}(i\le m)$ 的最优选法，所以每个方案至多包含 $X_{i}$ 的次优方案，所以每个方案的权值和 $\le$ $X_{1},…,X_{k}$ 的次优方案和 $X_{k+1}$ 的最优方案，而这个上界是能达到的，也就是上面那个东西，证毕。
时间复杂度：$O((n+k)\log{n+k}+m\log_{m})$ 。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 1e9;
const int N = 5e2 + 5;
const int M = 2e3 + 5;
int n, m, K, st, in[N];
vector<PII> e[N];
int fa[N], inc[N], outc[N];
int findfa(int x){return fa[x] == x ? x : fa[x] = findfa(fa[x]);}
void mer(int x, int y){
x = findfa(x);
y = findfa(y);
if(x != y){
fa[x] = y;
inc[y] += inc[x];
outc[y] += outc[x];
}
}
vector<int> u[N];
int main(){
int T;
cin >> T;
while(T--){
memset(in, 0, sizeof(in));
cin >> n >> m >> K >> st;
for(int i = 1; i <= m; i++) e[i].clear(), u[i].clear();
in[st]++;
for(int i = 1; i <= n; i++){
int x, c, y;
cin >> x >> c >> y;
e[x].push_back({c, y});
in[y]++;
}
for(int i = 1; i <= K; i++){
int x;
cin >> x;
in[x]++;
}
for(int i = 1; i <= m; i++){
fa[i] = i;
inc[i] = in[i];
outc[i] = 0;
}
LL ans = 0;
for(int i = 1; i <= m; i++){
sort(e[i].begin(), e[i].end(), [](PII x, PII y){return x.first > y.first;});
int cnt = in[i];
for(auto [c, y] : e[i]){
if(!cnt) break;
cnt--;
ans += c;
mer(i, y);
outc[findfa(i)]++;
}
}
for(int i = 1; i <= m; i++) u[findfa(i)].push_back(i);
for(int i = 1; i <= m; i++){
if(fa[i] == i && inc[i] == outc[i] && inc[i]){
int tmp = 1e9;
for(auto x : u[i]){
assert(in[x]);
if(e[x].size() > in[x]) tmp = min(tmp, e[x][in[x] - 1].first - e[x][in[x]].first);
else tmp = min(e[x].back().first, tmp);
}
ans -= tmp;
}
}
cout << ans << "\n";
}
return 0;
}
|
所以为什么才开到 $5000$ ，这么能诈骗，要是 $200000$ 我赛时就做这题了。
和官方题解基本一致，不过我是从保留的角度考虑的，题解是从删除的角度考虑的，本质是一样的。
