题解：P3651 展翅翱翔之时 (はばたきのとき)

· · 题解

哇今天早上模拟赛这题放 T2 结果倒闭倒闭倒闭，太开心了太开心了太开心了。

首先我们发现给出的是一个内向基环树森林，我们考虑把每一个基环树拆成链，这样直接连起来就做完了。

首先考虑环外的树边，我们发现对于一个点 u，只会留下连着 u 的最大权值的边，剩下的边就会随着跟到别的地方，设这个值为 f_u，但是这个值可能会在环上，也可能会在树边上，设在树边上的值为 g_u。

我们先把所有的边都改，然后对于每一个 u 的 f_u 一定不会改，所以减去。

然后我们再考虑环上的边，一定会断且只会断一条边，我们可以枚举这条边，那么我们再需要加上的代价就是 f_u-g_u，因为此时我要看一下就是把在环上 u 的这条边断掉，然后再加上连子树的代价，就是 f_u-g_u 了。

代码很好写，重构无数遍。

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_Start;
constexpr int N=1e5+10;
int _=1,n,ans=0,A[N],C[N],vis[N],maxn1[N],maxn2[N];
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}inline void files(){
    freopen("cost.in","r",stdin);
    freopen("cost.out","w",stdout);
}inline void clr(){
//  Don't Forget!

}bool Test_MLE_End;
signed main(){
//  printf("%lf Mb\n",(&Test_MLE_End-&Test_MLE_Start-1)/1024.0/1024.0);
    files();
//  _=reads();
    while(_--){
        clr();n=reads();
        for(int i=1;i<=n;i++) A[i]=reads(),C[i]=reads(),ans+=C[i];
        for(int i=1;i<=n;i++){
            if(vis[i]) continue;
            int now=i,cnt=0;
            while(!vis[now]) vis[now]=i,now=A[now];
            if(vis[now]!=i) continue;
            while(vis[now]==i) vis[now]=-1,now=A[now],cnt++;
            if(cnt==n) puts("0"),exit(0);
        }for(int i=1;i<=n;i++){
            maxn1[A[i]]=max(maxn1[A[i]],C[i]);
            if(vis[i]!=-1) maxn2[A[i]]=max(maxn2[A[i]],C[i]);
        }for(int i=1;i<=n;i++) ans-=maxn1[i];
        for(int i=1;i<=n;i++){
            if(vis[i]==-1){
                int minn=2e18;
                int now=i;
                while(vis[now]==-1) vis[now]=0,minn=min(minn,maxn1[now]-maxn2[now]),now=A[now];
                ans+=minn;
            }
        }printf("%lld\n",ans);
    }return 0;
}
/*
9
2 2
3 1
7 1
5 1
6 1
7 1
8 1
9 1
7 1

*/