本文迁移自洛谷原文。
题目意思很清楚不解释。
我们一共有 $n$ 个点，但只有 $n$ 条有向边，还想让这张图强连通，显然是要求我们把这张图变为一个环。
稍微思考一下即可发现，这个题目等价于保留代价最大的那些链，然后删掉剩余的边进行缝缝补补。（因为最后是要变为一个环，换上每个点的入读和出度均为 $1$，如果保留的不是链的形式那么肯定有点出度或者入度大于 $1$，肯定不合法）
回头看看这个图。$n$ 个点，$n$ 条边，是一个基环树的形式。按照套路把环和树分开来看。
对于一个树点，由于要删掉大部分边使得它的入度变为 $1$，我们就可以只保留到它的边权最大的那条边。
由于这张图可能是个基环树森林，我们需要把所有的环也拼接起来，所以说，每个环上至少要断开一个点。
对于一个环，我们令 $mx_i$ 表示点 $i$ 的所有树节点儿子到 $i$ 的那条边上权值的最大值，$sum_i$ 为这些权值的和。令 $val_i$ 表示环上指向 $i$ 的那个点到 $i$ 的这条边的边权。
统计 $cnt$ 为对于一个环 $ring$ 上面的点，满足 $val_i<mx_i$ 的点的个数。
如果这个环的 $cnt > 0$，那么我们想不断白不断（管它是环点还是树点，都只能有一条入边，且断了环边仍是合法的）。
如果这个环的 $cnt=0$，那么为了满足“每个环至少要断开一个点”这个条件，我们就要找到 $val_i-mx_i$ 最小的那个点断开，使得代价最小。
ps. 有一个特例，整张图只有一个大环，且这个大环包括了所有点的时候，它既不需要和其他环拼接，也不需要让其他树点挤进来，所以答案就是 $0$。
Code:
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
| #include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
vector<pair<int,int> >tos[mxn];
int n,a[mxn],c[mxn];
int used[mxn],cused;
int ord[mxn],cord;
int inring[mxn];
int sum[mxn],ma[mxn];
vector<vector<int> >rings;
inline void dfs(int x){
if(used[x]==cused){
ord[++cord]=x;
vector<int>ring;
for(int i=cord-1;i;--i){
inring[ord[i]]=1;
ring.push_back(ord[i]);
if(ord[i]==x)break;
}
rings.push_back(ring);
return;
}
if(used[x])return;
ord[++cord]=x;
used[x]=cused;
dfs(a[x]);
--cord;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>c[i];
g[i].push_back(a[i]);
tos[a[i]].push_back({i,c[i]});
}
for(int i=1;i<=n;++i){
if(!used[i]){
++cused;
cord=0;
dfs(i);
}
}
if(rings.size()==1 and rings[0].size()==n){
cout<<0<<endl;
return 0;
}
ll ans=0;
for(int i=1;i<=n;++i){
if(!inring[i]){
int mx=0,sm=0;
for(auto p:tos[i]){
mx=max(mx,p.second);
sm+=p.second;
}
ans+=sm-mx;
}
}
for(vector<int>ring:rings){
ll tot=0;
int cnt=0,tval,delta=0;
for(int i:ring){
int mx=0,sm=0;
for(auto p:tos[i]){
if(!inring[p.first]){
mx=max(mx,p.second);
sm+=p.second;
}else tval=c[p.first];
}
ma[i]=mx;
sum[i]=sm;
tot+=sum[i];
if(tval<mx)++cnt,delta+=mx-tval;
}
if(cnt==0){
ll res=11451491919810;
for(int i:ring){
int j=a[i];
res=min(res,tot-ma[j]+c[i]);
}
ans+=res;
}else ans+=tot-delta;
}
cout<<ans<<endl;
}
|