首页 > 代码库 > 清北学堂模拟day4 传球接力
清北学堂模拟day4 传球接力
【问题描述】
n 个小朋友在玩传球。 小朋友们用 1 到 n 的正整数编号。 每个小朋友有一个固定的传球
对象，第 i 个小朋友在接到球后会将球传给第 ai个小朋友， 并且第 i 个小朋友与第 ai个小朋
友之间的距离为 di。
一次传球接力是这样进行的：由一个小朋友发球，将球传给他的传球对象，之后接到球
的小朋友再将球传给自己的传球对象，如此传球若干次后停止。 期间，包括发球者在内，每
个小朋友至多只能拿到球一次。 一次传球接力的总距离是每次传球的距离的总和。
小朋友们想进行一次总距离最长的传球接力，现在需要你帮助他们求出满足上述要求的
传球接力的最长总距离。
【输入】
输入的第 1 行包含 1 个整数 n。
接下来的 n 行，第 i 行包含两个整数 ai 和 di，意义如题目中所述， 两个数间用一个空格
隔开。
【 输出】
输出包含 1 个数， 表示传球接力总距离的最大值。
【输入输出样例 1】
| pass.in | pass.out |
| 5 2 1 3 2 4 1 2 3 3 3 | 7 |
见选手目录下的 pass / pass1.in 与 pass / pass1.out
【输入输出样例 1 说明】
由第 5 个小朋友发球， 传给第 3 个小朋友，再传给第 4 个小朋友，总距离为 3+1+3=7
【输入输出样例 2】
见选手目录下的 pass / pass2.in 与 pass / pass2.out
【数据规模与约定】
对于 50%的数据， n≤1,000
对于 100%的数据， n≤500,000， 1≤ai≤n， ai≠i， 1≤di≤10,000
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#define ll long long/*类似于信息传递，注意环外的也要算*/using namespace std;const int maxn = 500500;int n,a[maxn],d[maxn],f[maxn],vis[maxn];ll w[maxn],cir_w[maxn],ans;bool in_cir;int cir,is_cir[maxn],cir_u;int read(){ char ch=getchar(); int x=0,f=1; while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();}; return x*f;}void dfs(int u){ vis[u] = 1; if(!vis[a[u]]){ dfs(a[u]); }else if(vis[a[u]] == 1){ cir++; in_cir = true; is_cir[u] = cir; cir_w[cir] = d[u]; cir_u = a[u]; f[a[u]] = d[u]; vis[u] = 2; return; } if(in_cir){ is_cir[u] = cir; cir_w[cir] += d[u]; f[a[u]] = d[u]; if(u == cir_u){ //cout<<"!!"<<u<<endl; in_cir = false; ans = max(ans,cir_w[cir]); } vis[u] = 2; return; } if(is_cir[a[u]]) w[u] = cir_w[is_cir[a[u]]] + d[u] - f[a[u]]; else w[u] = w[a[u]] + d[u]; ans = max(ans,w[u]); //cout<<u<<"!!"<<w[u]<<endl; vis[u] = 2; //cout<<u<<" "<<w[u]<<endl;}int main(){ int size = 256 << 20; // 256MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); freopen("pass.in","r",stdin); freopen("pass.out","w",stdout); n = read(); for(int i = 1;i <= n;i++){ a[i] = read(); d[i] = read(); } for(int i = 1;i <= n;i++){ if(!vis[i]) dfs(i); } cout<<ans<<endl; return 0;}
清北学堂模拟day4 传球接力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。