题解：P14401 [JOISC 2016] 电报 / Telegraph
ycy1124
·
·
题解
很有意思的贪心。/yiw
思路
为了方便描述我们接下来将修改一条边的代价作为他的边权，(x,y) 表示一条从 x 连向 y 的边。
由于环的每个节点的入度都为 $1$，我们可以先将所有入度大于等于 $2$ 的节点的除了边权最大的那条边全部删掉。为了方便，我们先不删环上的边，而是将所有连接环的不在环上的边删掉。此时我们的图变成了一些环和一些链。但这明显不是我们想要的答案，我们考虑继续调整。由于我们的最终图需要将所有的点都合并到一个环中，所以对于当前的所有环都必须要断掉至少一条边使其变成一条链。我们需要找到一种最小的断环代价。绘图发现，我们删掉环上的一条边的代价不仅仅是这条边的边权，我们还有可能将原来为了方便而删掉的直接连向环的非环边加回来。如下图：
此时我们的 $(5,4)$ 这条边是被删掉的，当我们删掉 $(3,4)$ 这条边后可以将 $(5,4)$ 这条边加回来，其任然是一条链并且少了删 $(5,4)$ 的代价。并且发现，我们环上删掉一条 $(x,y)$ 的边，就可以将连接 $y$ 的最大的边加回来使其还是一条链。因此我们可以对于所有的环上的边，如果其被删掉之后加回来的边的边权大于当前边的边权，我们就将其删掉。最后注意每个环都至少要删掉一条边。
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int a[N], c[N], rd[N], color[N], Color, n, ans, w[N];
vector <int> id[N];
queue <int> q;
__inline__ void bfs(int p) {
rd[a[p]] --;// 跑拓扑后入读不为 0 的节点即为环上节点
if(!rd[a[p]]) {
q.push(a[p]);
}
}
__inline__ void Bfs(int p) {
color[p] = Color;
id[Color].push_back(p);
if(!color[a[p]]) {
Bfs(a[p]);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i] >> c[i];
rd[a[i]] ++;
}
for(int i = 1; i <= n; i ++) {
if(rd[i] == 0) {
q.push(i);
}
}
while(q.size()) {
int u = q.front();
q.pop();
bfs(u);
}
for(int i = 1; i <= n; i ++) {
if(rd[i] && !color[i]) {
++ Color;
Bfs(i);
}
}
bool tag = 1;
for(int i = 1; i <= n; i ++) {
if(color[i] != 1) {
tag = 0;
}
}
if(tag) {// 只有一个环判掉
cout << 0;
return 0;
}
for(int i = 1; i <= n; i ++) {// 对于每个节点求连向他的最大边权。
if(color[i] == 0) {
w[a[i]] = max(w[a[i]], c[i]);
}
}
for(int i = 1; i <= n; i ++) {
if(!color[i]) {// 不为环上边就先将其删掉然后再将这个节点的入边中最大的加回来即可完成删除无用边的操作
ans += c[i];
ans -= w[i];
}
}
for(int i = 1; i <= Color; i ++) {
int Ans = -1e9;
for(auto it : id[i]) {// 枚举环边
if(-c[it] + w[a[it]] >= 0) {// 如果删掉其后花费更小必删
ans -= -c[it] + w[a[it]];
}
Ans = max(-c[it] + w[a[it]], Ans);
}
ans -= Ans;// 至少删掉一条边
if(Ans > 0) {
ans += Ans;
}
}
cout << ans;
return 0;
}
```