解題

首先縮點(diǎn)沒啥可說的，然后考慮枚舉這次逆行的邊。具體來(lái)說在正常的圖和反圖上各跑一次最長(zhǎng)路，然后注意減掉起點(diǎn)的貢獻(xiàn)，用拓?fù)渑判驅(qū)崿F(xiàn)(我這里瞎寫了個(gè)Bellman_Ford，其實(shí)在DAG上這好像和拓?fù)渑判虻膹?fù)雜度是一樣的=。=)

一個(gè)細(xì)節(jié)：注意可能整個(gè)圖是個(gè)強(qiáng)連通分量，所以答案初始是起點(diǎn)所在的強(qiáng)聯(lián)通分量的大小

1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005; 7 int dfn[N],low[N],col[N],stk[N],ins[N],inq[N],siz[N],dis[2][N]; 8 int p[N],noww[N],goal[N],P[N][2],Noww[N][2],Goal[N][2]; 9 int n,m,c,t1,t2,cnt,cnt0,cnt1,tot,top,ans; 10 queue<int> qs; 11 void link(int f,int t) 12 { 13 noww[++cnt]=p[f]; 14 goal[cnt]=t,p[f]=cnt; 15 } 16 void relink(int f,int t) 17 { 18 Noww[++cnt0][0]=P[f][0]; 19 Goal[cnt0][0]=t,P[f][0]=cnt0; 20 Noww[++cnt1][1]=P[t][1]; 21 Goal[cnt1][1]=f,P[t][1]=cnt1; 22 } 23 void Tarjan_SCC(int nde) 24 { 25 dfn[nde]=low[nde]=++tot; 26 stk[++top]=nde,ins[nde]=true; 27 for(int i=p[nde];i;i=noww[i]) 28 if(!dfn[goal[i]]) 29 Tarjan_SCC(goal[i]),low[nde]=min(low[nde],low[goal[i]]); 30 else if(ins[goal[i]]) 31 low[nde]=min(low[nde],low[goal[i]]); 32 if(dfn[nde]==low[nde]) 33 { 34 c++; int tmp; 35 do 36 { 37 tmp=stk[top--]; 38 ins[tmp]=false; 39 col[tmp]=c,siz[c]++; 40 }while(nde!=tmp); 41 } 42 } 43 void Bellman_Ford(int s,int t) 44 { 45 memset(dis[t],0xc0,sizeof dis[t]); 46 dis[t][s]=siz[s],qs.push(s),inq[s]=true; 47 while(!qs.empty()) 48 { 49 int tn=qs.front(); 50 qs.pop(),inq[tn]=false; 51 for(int i=P[tn][t];i;i=Noww[i][t]) 52 if(dis[t][Goal[i][t]]<dis[t][tn]+siz[Goal[i][t]]) 53 { 54 dis[t][Goal[i][t]]=dis[t][tn]+siz[Goal[i][t]]; 55 if(!inq[Goal[i][t]]) 56 qs.push(Goal[i][t]),inq[Goal[i][t]]=true; 57 } 58 } 59 } 60 int main() 61 { 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=m;i++) 64 scanf("%d%d",&t1,&t2),link(t1,t2); 65 for(int i=1;i<=n;i++) 66 if(!dfn[i]) Tarjan_SCC(i); 67 for(int i=1;i<=n;i++) 68 for(int j=p[i];j;j=noww[j]) 69 if(col[i]!=col[goal[j]]) 70 relink(col[i],col[goal[j]]); 71 Bellman_Ford(col[1],0),Bellman_Ford(col[1],1),ans=siz[col[1]]; 72 for(int i=1;i<=c;i++) 73 for(int j=P[i][1];j;j=Noww[j][1]) 74 ans=max(ans,dis[0][i]+dis[1][Goal[j][1]]-siz[col[1]]); 75 printf("%d",ans); 76 return 0; 77 } View Code

?

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

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的解题：USACO15JAN Grass Cownoisseur的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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