lp5145 漂浮的鸭子

一道tarjan缩点的裸题。
我们仍然可以考虑一个很有趣的做法。那就是，把非环边删去，然后统计环的边权。

#include<iostream>
#include<cstdio>

struct ee{
	int v;
	int w;
}e[100005];

int n,in[100005];
bool vis[100005];

void init(){
	scanf("%d",&n);
	int v,w;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&v,&w);
		e[i]=(ee){v,w};
		++in[v];
	}
	int ans=0,x,nw;
	for(int i=1;i<=n;++i){
		x=i;
		while(!in[x]&&!vis[x]){
			vis[x]=1;
			--in[e[x].v];
			x=e[x].v;
		}
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			nw=e[i].w;
			x=e[i].v;
			vis[i]=1;
			while(x!=i){
				vis[x]=1;
				nw+=e[x].w;
				x=e[x].v;
			}
			ans=std::max(ans,nw);
		}
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}