代码二楼:
```cpp
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 1000005;
struct edge{
int to, nxt;
}e[M << 1];
int head[M], cnt1, deg[M], n, a[M];
long long ans, val[M];
void link(int u, int v){
e[++cnt1].to = v; deg[v]++;
e[cnt1].nxt = head[u]; head[u] = cnt1;
}
int bl[M]; vector<int> s; queue<int> q; bool vis[M], vis2[M], circle[M];
void find(){
for(int i = 1; i <= n; i++) if(deg[i] == 1) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop(); vis[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to; deg[v]--;
if(deg[v] == 1) q.push(v);
}
} for(int i = 1; i <= n; i++) if(!vis[i]) circle[i] = 1;
}
long long dfs(int u, int fa){
// printf("%d\n", u);
vis2[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa || !circle[v]) continue;
if(v != a[u]) exit(-1); //经这一行测试确实有 v!=a[u] 出现
if(vis2[v]) return val[u];
return min(val[u], dfs(v, u));
}
return 0;
}
int main(){
freopen("2.in", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %lld", &a[i], &val[i]);
ans += val[i];
link(i, a[i]); link(a[i], i);
}
find();
for(int i = 1; i <= n; i++){
if(circle[i] && !vis2[i]){
ans -= dfs(i, 0);
}
}
printf("%lld\n", ans);
}
```
by Missa @ 2022-04-07 12:14:35
%%%
by Galex @ 2022-04-07 12:26:38
@[翁佳良](/user/483037) 不要膜一个橙题都不会的蒟蒻,会掉rp的
by Missa @ 2022-04-07 12:37:03
现在发现可能是顺着环往另一个方向搜了。
但是那也不应该WA啊。
by Missa @ 2022-04-07 12:38:19
![](//图.tk/ga)
by 暗影之梦 @ 2022-04-07 12:42:25
![](//图.tk/ga)
所以说$v$是指什么呀?环中单向遍历一遍算出最小边权从总边权减去里不就是答案吗?
by jer2021 @ 2022-04-07 14:14:13
关键点是,你连的是双向边啊......
并查集存双向边,但是你遍历需要沿着 $a_i$ 遍历啊......
如果我理解错误我自裁,这是我的离谱代码
```cpp
for (int i = 1; i <= N; ++i) if (!vis1[UFS::find(i)]) {
vis1[UFS::find(i)] = true; int p = i;
while (!vis2[p]) vis2[p] = true, p = a[p];
long long mv = 10000000000ll;
while (!vis3[p]) vis3[p] = true, mv = std::min(mv, v[p]), p = a[p];
ans -= mv;
}
```
by irris @ 2022-04-07 14:53:00
@[jer2021](/user/368723) $v$ 与 $u$ 相连,因为我连的是双向边,不一定是那个 $a_u$
by Missa @ 2022-04-07 16:12:31
@[AlgorithmerSnow](/user/419487) 确实应该顺着 $a_u$ 遍历,但是我先跑过一个求环的代码了,并且保证了不会走回头路且下一步在环上,应该确实会遍历一遍环啊
by Missa @ 2022-04-07 16:15:25
模拟赛考到了,写的也是内向基环树,同求
by Register_int @ 2022-10-22 19:53:38