[NEERC2007][SHOI2008]Cactus Reloaded

题目大意：
　　给你一个仙人掌，求图中相距最远的点对之间的距离。

思路：
　　Tarjan+DP。
　　我们先考虑一个树的情况。
　　设用far[u]表示点u出发到其子树中叶子节点的最大距离，若v为u的子结点，很显然far[u]=max{far[v]}+1。
　　而对于经过点u的简单路径，最长的一条肯定是max{far[v]+far[w]+2}，且u≠w。
　　很显然我们只需要DFS一遍，然后随便转移即可。
　　考虑一下仙人掌和树有什么不同。
　　很显然仙人掌就是在一棵树上加了几条边，使得图中出现了一些环，而且不会有边同时出现在两个环中。
　　我们不妨先把原图的环去掉某一个边，使得剩下的图是一棵树，很容易处理出树上的情况。
　　处理到当前环中最后一条边时，再单独对这个环进行DP。
　　考虑这个环上的每一棵外向树，设u和v是这个环上的两个结点，那么far[u]+far[v]+dis(u,v)就是一个可能的答案。
　　如何让这个答案最大化？
　　对于每一个点u，我们可以枚举每一个v来得到一个可能的答案，而要让答案尽可能大，似乎可以用单调队列来转移。
　　但唯一的问题是，现在u和v是再一个环上，他们的距离是不会单调递增的，也就是说你按顺序枚举每一个点，可能先越来越远再越来越近。
　　对于这种情况，我们把环复制一遍来转移，维护队列的时候要判断一下当前待更新的点u和用来更新的点v距离是不是超过环长的一半。
　　最后再更新一下环上高度最高的点对应的far值。
　　设环的大小为size，最高点为top，那么far[top]=max(far[top],max{far[v]+dis(top,v)})。
　　这时候要注意一下，前面DFS(Tarjan)里面，far的转移要判断一下，low[v]是不是大于等于dfn[u]，如果不是，说明现在是在环上。
　　所以不能直接更新，不然后面环上DP可能会重复。

 #include<queue>

 #include<cstdio>

 #include<cctype>

 #include<vector>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 std::vector<int> e[N];

 int far[N],par[N],ans;

 inline void add_edge(const int &u,const int &v) {

     e[u].push_back(v);

     e[v].push_back(u);

 }

 inline void dp(const int &top,const int &end,const int &size) {

     static int cir[N*];

     static std::deque<int> q;

     for(register int i=size,v=end;i;i--) {

         cir[size+i]=cir[i]=far[v];

         v=par[v];

     }

     q.push_back();

     for(register int i=;i<=size*;i++) {

         if(i-q.front()>size/) q.pop_front();

         ans=std::max(ans,cir[i]+cir[q.front()]+i-q.front());

         while(!q.empty()&&cir[q.back()]-q.back()<=cir[i]-i) q.pop_back();

         q.push_back(i);

     }

     q.clear();

     for(register int i=;i<=size;i++) {

         far[top]=std::max(far[top],cir[i]+std::min(i-,size-i+));

     }

 }

 void tarjan(const int &x,const int &par) {

     static int low[N],dfn[N],dep[N],cnt;

     ::par[x]=par;

     dep[x]=dep[par]+;

     low[x]=dfn[x]=++cnt;

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         if(!dfn[y]) {

             tarjan(y,x);

             low[x]=std::min(low[x],low[y]);

         } else {

             low[x]=std::min(low[x],dfn[y]);

         }

         if(dfn[x]<low[y]) {

             ans=std::max(ans,far[x]+far[y]+);

             far[x]=std::max(far[x],far[y]+);

         }

     }

     for(register unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(x!=::par[y]&&dfn[x]<dfn[y]) {

             dp(x,y,dep[y]-dep[x]+);

         }

     }

 }

 int main() {

     getint();

     for(register int m=getint();m;m--) {

         for(register int k=getint(),u=getint();--k;) {

             const int v=getint();

             add_edge(u,v);

             u=v;

         }

     }

     tarjan(,);

     printf("%d\n",ans);

     return ;

 }

巴特西

[NEERC2007][SHOI2008]Cactus Reloaded

最新文章

热门文章