[IOI2008]Island

本文主要是介绍[IOI2008]Island，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

思路：

• 无向基环树森林求直径和。
• 对于每颗基环树，它对答案的贡献只有可能经过环或不经过，分类讨论即可。
• 首先处理出每个点往下的最大深度，顺便进行树形DP，再用单调队列获取经过环时的答案即可。
• 最终树形DP与单调队列的结果取max即可。
• （注意内存，数组需要使用技巧二次利用）

---

 （该代码内存超限）

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC optimize ("O3")
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=2000020,MAXM=1000010;
int n;
struct Edge{int from,to,w,nxt;
}e[MAXN];
int head[MAXN],edgeCnt=1,degree[MAXN];
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
queue<int> topoQueue;
void topoSort(){for(int i=1;i<=n;i++)if(degree[i]==1)topoQueue.push(i);while(!topoQueue.empty()){int nowV=topoQueue.front();topoQueue.pop();for(int i=head[nowV];i;i=e[i].nxt){int v=e[i].to;degree[v]--,degree[nowV]--;if(degree[v]==1)topoQueue.push(v);}}
}
bool First_vis_circle[MAXN];
deque<int> First_circles[MAXN];int First_circleCnt=0;
long long First_dist[MAXN];
void First_find_Circle(int x,long long dis){First_vis_circle[x]=1;First_dist[x]=dis;First_circles[First_circleCnt].push_back(x);for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;if(!First_vis_circle[v]&&degree[v]>=2){First_find_Circle(v,e[i].w+dis);}}
}
bool Second_vis_circle[MAXN];
long long Second_dist[MAXN];
deque<int> Second_circles[MAXN];int Second_circleCnt=0;
void Second_find_Circle(int x,long long dis,bool isFirst){Second_vis_circle[x]=1;Second_dist[x]=dis;Second_circles[Second_circleCnt].push_back(x);for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;if(!Second_vis_circle[v]&&degree[v]>=2){if(isFirst){isFirst=false;continue;}Second_find_Circle(v,e[i].w+dis,0);}}
}
long long d[MAXN];
bool vis_dp[MAXN];
long long ans[MAXN],nowRoot=0;
long long circle_deep_ans[MAXN]; 
void dfs_dp(int x,int in_edge,int in_circle){vis_dp[x]=1;for(int i=head[x];i;i=e[i].nxt){ if(i==(in_edge^1))continue;int v=e[i].to;if(degree[v]<2&&(!vis_dp[v])){dfs_dp(v,i,in_circle);ans[x]=max(ans[x],d[x]+d[v]+e[i].w);circle_deep_ans[in_circle]=max(circle_deep_ans[in_circle],ans[x]);d[x]=max(d[x],d[v]+e[i].w);}}
}
int First_a[MAXN],First_endIndex=0;
int First_q[MAXN];
long long First_ans_point_to_point[MAXN],First_ans_point_to_pointCnt=0;
int Second_a[MAXN],Second_endIndex=0;
int Second_q[MAXN];
long long Second_ans_point_to_point[MAXN],Second_ans_point_to_pointCnt=0;
long long across_ans[MAXN];//直径 
long long total_across_ans=0;
int main(){memset(across_ans,0xcf,sizeof(across_ans));scanf("%d",&n);for(int i=1;i<=n;i++){int v,w;scanf("%d%d",&v,&w);addEdge(i,v,w);addEdge(v,i,w);degree[v]++;degree[i]++;}topoSort();for(int i=1;i<=n;i++){if(!First_vis_circle[i]&&degree[i]>=2){First_circleCnt++;First_find_Circle(i,0);}}for(int i=1;i<=n;i++){if(!Second_vis_circle[i]&&degree[i]>=2){Second_circleCnt++;Second_find_Circle(i,0,1);}}for(int i=1;i<=First_circleCnt;i++){int first=First_endIndex+1,size=First_circles[i].size();First_endIndex=first+2*size-1;int nowIndex=first;while(!First_circles[i].empty()){int nowV=First_circles[i].front();First_circles[i].pop_front();dfs_dp(nowV,0,i);First_a[nowIndex]=nowV;First_a[nowIndex+size]=nowV;nowIndex++;First_endIndex=nowIndex;}int l,r;First_q[l=r=1]=first;First_ans_point_to_pointCnt++;for(int j=first+1;j<=First_endIndex;j++){while(l<r&&j-First_q[l]>=size)l++;First_ans_point_to_point[First_ans_point_to_pointCnt]=max(First_ans_point_to_point[First_ans_point_to_pointCnt],d[First_a[j]]+d[First_a[First_q[l]]]+First_dist[First_a[j]]-First_dist[First_a[First_q[l]]]);while(l<r&&d[First_q[r]]-First_dist[First_q[r]]<d[First_a[j]]-First_dist[First_a[j]])r--;First_q[++r]=j;}}for(int i=1;i<=Second_circleCnt;i++){int first=Second_endIndex+1,size=Second_circles[i].size();Second_endIndex=first+2*size-1;int nowIndex=first;while(!Second_circles[i].empty()){int nowV=Second_circles[i].front();Second_circles[i].pop_front();dfs_dp(nowV,0,i);Second_a[nowIndex]=nowV;Second_a[nowIndex+size]=nowV;nowIndex++;Second_endIndex=nowIndex;}int l,r;Second_q[l=r=1]=first;Second_ans_point_to_pointCnt++;for(int j=first+1;j<=Second_endIndex;j++){while(l<r&&j-Second_q[l]>=size)l++;Second_ans_point_to_point[Second_ans_point_to_pointCnt]=max(Second_ans_point_to_point[Second_ans_point_to_pointCnt],d[Second_a[j]]+d[Second_a[Second_q[l]]]+Second_dist[Second_a[j]]-Second_dist[Second_a[Second_q[l]]]);while(l<r&&d[Second_a[Second_q[r]]]-Second_dist[Second_a[Second_q[r]]]<d[Second_a[j]]-Second_dist[Second_a[j]])r--;Second_q[++r]=j;}}for(int i=1;i<=First_ans_point_to_pointCnt;i++){across_ans[i]=max(across_ans[i],First_ans_point_to_point[i]);}long long trueAns=0;for(int i=1;i<=Second_ans_point_to_pointCnt;i++){across_ans[i]=max(across_ans[i],Second_ans_point_to_point[i]);trueAns+=max(across_ans[i],circle_deep_ans[i]);}cout<<trueAns<<endl;return 0;
}

 

这篇关于[IOI2008]Island的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---