https://www.luogu.org/problem/show?pid=3119
本來我是來練習tarjan的，結(jié)果tarjan部分直接copy了，反而拓撲排序部分想了好久；
這道題SZB大神兩次就AC；
但我等到AC，寫好題解就只能洗洗睡了；
唉~
差距怎么這么大呢？；
這道題的題意就說，你可以改變一條邊的方向，去找到一個環(huán)，讓環(huán)上的點數(shù)最大；
網(wǎng)上的題解，大多都在嚷嚷tarjan+拓撲排序最長鏈；
我先講講什么是拓撲排序最長鏈把；

---

很顯然啊，上面的圖里，1~3的最長鏈是3；
我們考慮一下最樸素的dfs;
我們從1開始，先搜索到了3；
這個時候我們把1~3的最長鏈更新為 1-3，就是2個節(jié)點；
假如3出度有好多，那么凡是3后面的點我們都要遍歷一邊；
然后遍歷完3，我發(fā)現(xiàn) 1~3的最長鏈不是1-3而是1-2-3;
原先的1~3最長鏈的節(jié)點個數(shù)2被更新為3；
這個時候我們發(fā)現(xiàn)原來3連出去的點，他們與1的最長鏈都不是最優(yōu)的;
所以我們又要dfs一遍；
這樣太煩了；
那怎么辦呢？
看到這里，我想您一定知道什么是拓撲排序最長鏈了；
對啊，假如我們搜索到3的時候先不去往后面搜索，先去遍歷2；
這樣1~3的最長鏈會被及時更新，3后面的節(jié)點就不用重復更新了；
其實這樣就是按照拓撲排序的順序去遍歷節(jié)點啊，不斷找入度為0的節(jié)點去更新其它節(jié)點；
這就是拓撲排序最長鏈

---

這道題就簡單了啊；
我先縮點一下，讓這個有環(huán)圖變成有向無環(huán)圖；
然后用一個dfs去算出那些點可以到達1；那些點會從1到達；
分別算出這些點到1的最長鏈，然后枚舉每一條邊，看看把這條邊反一下，加上兩端到1的最長鏈然后更新ans就好啦；
很顯然啊，這兩條鏈不會重復，因為他們的方向是不同的；
我的超級優(yōu)美的代碼，60行！；

超級無敵大壓行！！！！

#include<cstdio>//cfb #include<iostream> #include<cstring> using namespace std; struct cs{int to,next;}a[100001]; //lin[i]是i再那個分量里面 sum[i]就是第i個分量有幾個點 d[i]是當前分量i的入度 int head[100001],low[100001],tt[100001],q[100001],lin[100001],cc[100001][2],sum[100001],A[100001][1],d[100001]; bool in[100001],AA[100001][2];//AA[i][0]表示1是否可以到i，[1]是i是否可以到j;A[i][0/1]即他們的最長鏈 int ll,n,m,x,y,z,t,nn,l,r,ans; void init(int x,int y){a[++ll].to=y; a[ll].next=head[x]; head[x]=ll;} void dfs(int x){ tt[x]=++t; low[x]=t; q[++q[0]]=x; in[x]=1; for(int k=head[x];k;k=a[k].next){ if(!tt[a[k].to])dfs(a[k].to); if(in[a[k].to])low[x]=min(low[x],low[a[k].to]); } if(low[x]==tt[x]){ nn++; while(1){ in[q[q[0]]]=0; lin[q[q[0]]]=nn; q[0]--; sum[nn]++; if(q[q[0]+1]==x)break; } } } void make(int x,int num){//然后用一個dfs去算出那些點可以到達1；那些點會從1到達； in[x]=1; AA[x][num]=1; for(int k=head[x];k;k=a[k].next){d[a[k].to]++; if(!in[a[k].to])make(a[k].to,num);} } void TP(int num){//拓撲排序 r=1; q[1]=lin[1]; A[lin[1]][num]=0; make(lin[1],num); while(r>l){ x=q[++l]; for(int k=head[x];k;k=a[k].next){ A[a[k].to][num]=max(A[a[k].to][num],A[x][num]+sum[a[k].to]); d[a[k].to]--; if(!d[a[k].to])q[++r]=a[k].to; } } } void S(){ memset(q,0,sizeof q);memset(head,0,sizeof head); memset(d,0,sizeof d);memset(in,0,sizeof in); ll=0; r=l=0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){scanf("%d%d",&cc[i][0],&cc[i][1]);init(cc[i][0],cc[i][1]);} for(int i=1;i<=n;i++)if(!tt[i])dfs(i); S(); for(int i=1;i<=m;i++){x=cc[i][0]; y=cc[i][1]; if(lin[x]!=lin[y])init(lin[x],lin[y]);} TP(0); S(); for(int i=1;i<=m;i++){x=cc[i][0]; y=cc[i][1]; if(lin[x]!=lin[y])init(lin[y],lin[x]);} TP(1); for(int i=1;i<=m;i++){ x=lin[cc[i][0]]; y=lin[cc[i][1]]; if(x==y||!AA[y][0]||!AA[x][1])continue; ans=max(ans,A[y][0]+A[x][1]); } printf("%d",ans+sum[lin[1]]); }

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

總結(jié)

以上是生活随笔為你收集整理的拓扑排序最长链-P3119 [USACO15JAN]草鉴定Grass Cownoisseur的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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