Description
题目描述
你准备浏览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿 i 出发向另外一个岛屿建了一座长度为 L_i 的桥，
不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。
你希望经过的桥的总长度尽可能长，但受到以下的限制：
1.步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
2.渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 SS 走到 DD
(当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。
注意，你不必游览所有的岛，也可能无法走完所有的桥。
请你编写一个程序，给定 NN 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。
输入格式
第一行包含 NN 个整数，即公园内岛屿的数目。
随后的 NN 行每一行用来表示一个岛。第 ii 行由两个以单空格分隔的整数，表示由岛 ii 筑的桥。
第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 L_i。
你可以假设对于每座桥，其端点总是位于不同的岛上。
输出格式
仅包含一个整数，即可能的最大步行距离。
Solution
读入
int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%lld",&x,&y); link[i].push_back((node){x,y}); link[x].push_back((node){i,y}); } }
由题意可知当只把桥加入图中时，每个点的出度为 1 ，且一共有N条边，
这不就是外向基环树森林的模型吗。
由要求知，只能在两棵基环树间乘坐渡船（其他情况下可由桥到达），
且乘坐渡船从一棵基环树出去后不能再返回这棵树
于是我们求出每棵基环树的直径并累计
（基环树中最长的简单路径被称为基环树的最长链，其长度被称为基环树的直径。
这里，简单路径指的是不自交（不重复经过任何点或边）的路径）
基环树直径的求法
void dfs(int u,int fx) { flag[u]=true,fa[u]=fx; int size=link[u].size(); int cnt=0; for(int i=0;i<size;i++) { int v=link[u][i].v; if((v==fx && ++cnt==1) || cir[v]) continue; if(flag[v]) { int x=u; while(x!=v) a[++a[0]]=x,d[++d[0]]=w[x],cir[x]=true,x=fa[x]; cir[v]=true,a[++a[0]]=v,d[++d[0]]=link[u][i].w; } else w[v]=link[u][i].w,dfs(v,u); } }
void dfs1(int u,int fx,ll res,ll &x) { int size=link[u].size(); for(int i=0;i<size;i++) { int v=link[u][i].v; if(v==fx || cir[v]) continue; dfs1(v,u,res+link[u][i].w,x); if(b[u][0]<b[v][0]+link[u][i].w) { b[u][1]=b[u][0]; b[u][0]=b[v][0]+link[u][i].w; } else b[u][1]=max(b[u][1],b[v][0]+link[u][i].w); } x=max(x,max(res+b[u][0],b[u][0]+b[u][1])); }
for(int i=1;i<=n;i++) if(!flag[i]) { d[0]=0,a[0]=0,dfs(i,0); an=0; for(int j=1;j<=a[0];j++) dfs1(a[j],0,0,an),ma[j]=b[a[j]][0]; ll cc=d[d[0]]; for(int j=d[0];j>1;j--) d[j]=d[j-1]; d[1]=cc; d[0]=0; for(int j=a[0]+1;j<=a[0]*2;j++) ma[j]=ma[j-a[0]],d[j]=d[j-a[0]]; for(int j=1;j<=a[0]*2;j++) d[j]+=d[j-1]; l=1,r=0; for(int j=1;j<=2*a[0];j++) { while(l<=r && j-q[l]>=a[0]) l++; if(l<=r) an=max(an,ma[q[l]]-d[q[l]]+d[j]+ma[j]); while(l<=r && ma[q[r]]-d[q[r]]<=ma[j]-d[j]) r--; q[++r]=j; } ans+=an; }
Code
#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #define ll long long using namespace std; const int N=1e6+10; bool flag[N],cir[N]; struct node { int v; ll w; }; vector <node> link[N]; int x,n,fa[N],a[N*2],q[N*2],l,r; ll ans,y,d[N*2],w[N],ma[N*2],b[N][2],an; void dfs(int u,int fx) { flag[u]=true,fa[u]=fx; int size=link[u].size(); int cnt=0; for(int i=0;i<size;i++) { int v=link[u][i].v; if((v==fx && ++cnt==1) || cir[v]) continue; if(flag[v]) { int x=u; while(x!=v) a[++a[0]]=x,d[++d[0]]=w[x],cir[x]=true,x=fa[x]; cir[v]=true,a[++a[0]]=v,d[++d[0]]=link[u][i].w; } else w[v]=link[u][i].w,dfs(v,u); } } void dfs1(int u,int fx,ll res,ll &x) { int size=link[u].size(); for(int i=0;i<size;i++) { int v=link[u][i].v; if(v==fx || cir[v]) continue; dfs1(v,u,res+link[u][i].w,x); if(b[u][0]<b[v][0]+link[u][i].w) { b[u][1]=b[u][0]; b[u][0]=b[v][0]+link[u][i].w; } else b[u][1]=max(b[u][1],b[v][0]+link[u][i].w); } x=max(x,max(res+b[u][0],b[u][0]+b[u][1])); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%lld",&x,&y); link[i].push_back((node){x,y}); link[x].push_back((node){i,y}); } for(int i=1;i<=n;i++) if(!flag[i]) { d[0]=0,a[0]=0,dfs(i,0); an=0; for(int j=1;j<=a[0];j++) dfs1(a[j],0,0,an),ma[j]=b[a[j]][0]; ll cc=d[d[0]]; for(int j=d[0];j>1;j--) d[j]=d[j-1]; d[1]=cc; d[0]=0; for(int j=a[0]+1;j<=a[0]*2;j++) ma[j]=ma[j-a[0]],d[j]=d[j-a[0]]; for(int j=1;j<=a[0]*2;j++) d[j]+=d[j-1]; l=1,r=0; for(int j=1;j<=2*a[0];j++) { while(l<=r && j-q[l]>=a[0]) l++; if(l<=r) an=max(an,ma[q[l]]-d[q[l]]+d[j]+ma[j]); while(l<=r && ma[q[r]]-d[q[r]]<=ma[j]-d[j]) r--; q[++r]=j; } ans+=an; } printf("%lld\n",ans); return 0; }
void dfs(int u,int fx){flag[u]=true,fa[u]=fx;int size=link[u].size();int cnt=0;for(int i=0;i<size;i++){int v=link[u][i].v;if((v==fx && ++cnt==1) || cir[v]) continue;if(flag[v]){int x=u;while(x!=v) a[++a[0]]=x,d[++d[0]]=w[x],cir[x]=true,x=fa[x];cir[v]=true,a[++a[0]]=v,d[++d[0]]=link[u][i].w;}else w[v]=link[u][i].w,dfs(v,u);}}
原文：https://www.cnblogs.com/hsez-cyx/p/12327439.html