专栏文章

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

IInnitTimmer_
P3651题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2ddvi
此快照首次捕获于
2025/12/01 19:26
3 个月前
此快照最后确认于
2025/12/01 19:26
3 个月前
查看原文
哇今天早上模拟赛这题放 T2 结果倒闭倒闭倒闭，太开心了太开心了太开心了。
首先我们发现给出的是一个内向基环树森林，我们考虑把每一个基环树拆成链，这样直接连起来就做完了。
首先考虑环外的树边，我们发现对于一个点 uu，只会留下连着 uu 的最大权值的边，剩下的边就会随着跟到别的地方，设这个值为 fuf_u，但是这个值可能会在环上，也可能会在树边上，设在树边上的值为 gug_u。
我们先把所有的边都改，然后对于每一个 uu 的 fuf_u 一定不会改，所以减去。
然后我们再考虑环上的边，一定会断且只会断一条边，我们可以枚举这条边，那么我们再需要加上的代价就是 fu−guf_u-g_u，因为此时我要看一下就是把在环上 uu 的这条边断掉，然后再加上连子树的代价，就是 fu−guf_u-g_u 了。
代码很好写，重构无数遍。
CPP
#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

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...