Description
如果某個無向連通圖的任意一條邊至多只出現(xiàn)在一條簡單回路（simple cycle）里，我們就稱這張圖為仙人掌圖（cactus）。所謂簡單回路就是指在圖上不重復(fù)經(jīng)過任何一個頂點(diǎn)的回路。

舉例來說，上面的第一個例子是一張仙人圖，而第二個不是——注意到它有三條簡單回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同時出現(xiàn)在前兩個的簡單回路里。另外，第三張圖也不是仙人圖，因為它并不是連通圖。顯然，仙人圖上的每條邊，或者是這張仙人圖的橋（bridge），或者在且僅在一個簡單回路里，兩者必居其一。定義在圖上兩點(diǎn)之間的距離為這兩點(diǎn)之間最短路徑的距離。定義一個圖的直徑為這張圖相距最遠(yuǎn)的兩個點(diǎn)的距離。現(xiàn)在我們假定仙人圖的每條邊的權(quán)值都是1，你的任務(wù)是求出給定的仙人圖的直徑。

Input
輸入的第一行包括兩個整數(shù)n和m（1≤n≤50000以及0≤m≤10000）。其中n代表頂點(diǎn)個數(shù)，我們約定圖中的頂點(diǎn)將從1到n編號。接下來一共有m行。代表m條路徑。每行的開始有一個整數(shù)k（2≤k≤1000），代表在這條路徑上的頂點(diǎn)個數(shù)。接下來是k個1到n之間的整數(shù)，分別對應(yīng)了一個頂點(diǎn)，相鄰的頂點(diǎn)表示存在一條連接這兩個頂點(diǎn)的邊。一條路徑上可能通過一個頂點(diǎn)好幾次，比如對于第一個樣例，第一條路徑從3經(jīng)過8，又從8返回到了3，但是我們保證所有的邊都會出現(xiàn)在某條路徑上，而且不會重復(fù)出現(xiàn)在兩條路徑上，或者在一條路徑上出現(xiàn)兩次。

Output
只需輸出一個數(shù)，這個數(shù)表示仙人圖的直徑長度。

Sample Input 1
15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10

Sample Output 1
8

Sample Input 2
10 1
10 1 2 3 4 5 6 7 8 9 10

Sample Output 2
9

HINT
對第一個樣例的說明：如圖，6號點(diǎn)和12號點(diǎn)的最短路徑長度為8，所以這張圖的直徑為8。

【注意】使用Pascal語言的選手請注意：你的程序在處理大數(shù)據(jù)的時候可能會出現(xiàn)棧溢出。
如果需要調(diào)整棧空間的大小，可以在程序的開頭填加一句：{$M 5000000}，其中5000000即
指代棧空間的大小，請根據(jù)自己的程序選擇適當(dāng)?shù)臄?shù)值。

---

首先建立一棵圓方樹，記每個環(huán)上dfs序最小的點(diǎn)為\(x_i\)，則每個環(huán)代表的方點(diǎn)向各自所擁有的\(x_i\)連一條邊權(quán)為1的邊，環(huán)上其他的圓點(diǎn)向方點(diǎn)連一條邊權(quán)為圓點(diǎn)到所屬\(x_i\)最短距離的邊

然后我們求圓方樹的直徑，顯然是需要記錄一條最長鏈\((f[i])\)和次長鏈\((g[i])\)的。如果當(dāng)前點(diǎn)是圓點(diǎn)，則直接用\(f[i]+g[i]\)更新答案；如果當(dāng)前點(diǎn)是方點(diǎn)，則考慮環(huán)上所有點(diǎn)(除去每個環(huán)內(nèi)的\(x_i\)，因為在圓方樹上\(x_i\)是方點(diǎn)的父親)，按照一定順序，用單調(diào)隊列維護(hù)\(f[i]+f[j]+dis(i,j)\)的最大值即可

單調(diào)隊列那里顯然要破環(huán)成鏈然后倍長……但是我發(fā)現(xiàn)我沒有倍長也過了……

/*program from Wolfycz*/ #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x7f7f7f7f using namespace std; typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline int frd(){int x=0,f=1; char ch=gc();for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';return x*f; } inline int read(){int x=0,f=1; char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';return x*f; } inline void print(int x){if (x<0) putchar('-'),x=-x;if (x>9) print(x/10);putchar(x%10+'0'); } const int N=1e5,M=2e5; int V[N+10],deep[N+10],dfn[N+10],belong[N+10]; int n,m,Ans,cnt; vector<int>vec[N+10]; int dis(int x,int y,int pos){if (!x||!y) return 0;if (dfn[x]<dfn[y]) swap(x,y);return min(deep[x]-deep[y],V[pos]-deep[x]+deep[y]); } struct S1{int pre[(M<<1)+10],now[M+10],child[(M<<1)+10],val[(M<<1)+10],tot;int f[M+10],g[M+10],fa[M+10];void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}int work(int pos){static int h[(N<<1)+10];int head=1,tail=0,res=0; h[1]=0;//記得清空h[1]for (vector<int>::iterator it=vec[pos].begin();it!=vec[pos].end();it++){if (it==vec[pos].begin()) continue;while (head<=tail&&(dis(h[head],*it,pos)>V[pos]/2||h[head]==*it)) head++;res=max(res,f[*it]+f[h[head]]+dis(h[head],*it,pos));while (head<=tail&&f[h[tail]]<=f[*it]) tail--;h[++tail]=*it;}for (vector<int>::iterator it=vec[pos].begin();it!=vec[pos].end();it++){if (it==vec[pos].begin()) continue;while (head<=tail&&(dis(h[head],*it,pos)>V[pos]/2||h[head]==*it)) head++;res=max(res,f[*it]+f[h[head]]+dis(h[head],*it,pos));while (head<=tail&&f[h[tail]]<=f[*it]) tail--;h[++tail]=*it;}return res;}void dfs(int x){for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){if (son==fa[x]) continue;fa[son]=x,dfs(son);int V=f[son]+val[p];if (f[x]<V) g[x]=f[x],f[x]=V;else if (g[x]<V) g[x]=V;}if (x<=n) Ans=max(Ans,f[x]+g[x]);else Ans=max(Ans,work(x-n));} }RST;//Round Square Tree struct S2{int pre[(M<<1)+10],now[N+10],child[(M<<1)+10];int fa[N+10],stack[N+10],low[N+10];int Time,tot,top,num;bool instack[N+10];void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}void insert(int x,int y){join(x,y),join(y,x);}void dfs(int x){dfn[x]=++Time,deep[x]=deep[fa[x]]+1;for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){if (son==fa[x]) continue;if (!dfn[son]){fa[son]=x;dfs(son);}else if (dfn[son]<dfn[x]){V[++cnt]=deep[x]-deep[son]+1;vec[cnt].push_back(son),RST.insert(cnt+n,son,0);for (int i=x;i!=son;i=fa[i]) vec[cnt].push_back(i),RST.insert(cnt+n,i,dis(i,son,cnt));}}}void tarjan(int x){dfn[x]=low[x]=++Time;instack[stack[++top]=x]=1;for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){if (son==fa[x]) continue;if (!dfn[son]) tarjan(son),low[x]=min(low[x],low[son]);else if (instack[son]) low[x]=min(low[x],dfn[son]);}if (low[x]==dfn[x]){instack[x]=0,belong[x]=++num;while (stack[top]!=x) instack[stack[top]]=0,belong[stack[top--]]=num;top--;}}void init(){Time=0;memset(dfn,0,sizeof(dfn));} }OT;//Original Tree struct S3{int x,y;void insert(int _x,int _y){x=_x,y=_y;} }Line[M+10]; int main(){n=read(),m=read();int L_cnt=0;for (int i=1;i<=m;i++){int k=read(),last=read();for (int j=1;j<k;j++){int x=read();OT.insert(last,x);Line[++L_cnt].insert(last,x);last=x;}}OT.dfs(1),OT.init(),OT.tarjan(1);for (int i=1;i<=L_cnt;i++)if (belong[Line[i].x]!=belong[Line[i].y])RST.insert(Line[i].x,Line[i].y,1);RST.dfs(1);printf("%d\n",Ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Wolfycz/p/10284295.html

總結(jié)

以上是生活随笔為你收集整理的[SHOI2008]cactus仙人掌图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。