研华acdp手机版_acwing算法基础

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

你准备游览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。

同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。

相对于乘船而言，你更喜欢步行。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制：

可以自行挑选一个岛开始游览。
任何一个岛都不能游览一次以上。
无论任何时间你都可以由你现在所在的岛 S 去另一个你从未到过的岛 D。由 S 到 D 可以有以下方法：
（1）步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
（2）渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。
注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。

输入格式
第 1 行包含整数 N。

第 2…N+1 行，每行包含两个整数 a 和 L，第 i+1 行表示岛屿 i 上建了一座通向岛屿 a 的桥，桥的长度为 L。

输出格式
输出一个整数，表示结果。

对某些测试，答案可能无法放进 32−bit 整数。

数据范围
2≤N≤106,
1≤L≤108

输入样例：
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
输出样例：
24

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int M = 2 * N;
ll st[N],ins[N];
//pox_cir 保留每一个环的末尾位置
ll pox_cir[N],cir[N],pre[N],tw[N];
ll prew[N],a[2 * N],s[2 * N],cnt_cir = 0;
ll d[N],da[N];
struct { 

ll v,next,w;
}edge[M];
ll head[N],cnt;
ll ans = 0;
ll q[2 * N],hh = 0,tt = 0;
void add(int u,int v,int w){ 

edge[cnt].w = w;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
ll max(ll &a ,ll &b){ 

return  a > b ? a : b;
}
void dfs_c(int u,int from){ 

st[u] = ins[u] = true;
for(int i = head[u];~i;i = edge[i].next){ 

if((i ^ 1) == from)continue;
ll v = edge[i].v,w = edge[i].w;
pre[v] = u,prew[v] = w;
if(!st[v])dfs_c(v,i);
else if(ins[v]){ 

cnt_cir ++;
pox_cir[cnt_cir] = pox_cir[cnt_cir - 1];
for(int k = u;k != v;k = pre[k]){ 

tw[k] = prew[k];
cir[++ pox_cir[cnt_cir]] = k;
}
tw[v] = prew[v],cir[++ pox_cir[cnt_cir]] = v;
}
}
ins[u] = false;
}
ll dfs_d(int u,int fa){ 

ll d1 = 0,d2 = 0;
for(int i = head[u];~i; i = edge[i].next){ 

ll v = edge[i].v,w = edge[i].w;
if(v == fa || st[v])continue;
ll d = dfs_d(v,u) + w;
if(d >= d1)d2 = d1,d1 = d;
else if(d > d2)d2 = d;
}
ans = max(ans,d1 + d2);
return d1;
}
int main(){ 

int n;
memset(head,-1,sizeof head);
cin>>n;
int x,w;
for(int i = 1;i <= n;i ++){ 

scanf("%d %d",&x,&w);
add(i,x,w),add(x,i,w);
}
for(int i = 1;i <= n;i ++){ 

if(!st[i]){ 

dfs_c(i,-1);
}
}
// cout<<cnt_cir<<endl;
// for(int i = 1;i <= pox_cir[cnt_cir];i ++){ 

// cout<<cir[i]<<" ";
// }
memset(st,0,sizeof st);
for(int i = 1;i <= pox_cir[cnt_cir];i ++)st[cir[i]] = true;
ll res = 0;
for(int i = 1;i <= cnt_cir;i ++){ 

ll ss = pox_cir[i - 1] + 1,ee = pox_cir[i];
ll aans = 0;
for(ll j = ss;j <= ee;j ++){ 

ll v = cir[j];
ans = 0;
ll res = dfs_d(v,-1);
d[v] = res,da[v] = ans;
aans = max(aans,da[v]);
}
int m = ee - ss + 1;
for(ll i = 0;i < m;i ++){ 

a[i] = cir[ee - i];
if(i != 0)s[i] = s[i - 1] + tw[a[i]];
else s[i] = tw[a[i]];
}
for(int i = 0;i < m - 1;i ++)a[i + m] = a[i],s[i + m] = s[i + m - 1] + tw[a[i + m]];
// for(int i = 0;i < 2 * m - 1;i ++){ 

// cout<<a[i]<<" "<<s[i]<<endl;
// }
hh = tt = 0;
ll t = 0;
for(int i = 0;i < 2 * m - 2;i ++){ 

if(hh != tt && q[hh] <= i - (m - 1))hh ++;
while(hh != tt && d[a[q[tt - 1]]] - s[q[tt - 1]] <= d[a[i]] - s[i])tt --;
q[tt ++] = i;
if(i >= m - 2){ 

aans = max(aans,d[a[i + 1]] + s[i + 1] + d[a[q[hh]]] - s[q[hh]]);
}
}
res += aans;
}
printf("%lld\n",res);
return 0;
}