題目鏈接：http://poj.org/problem?id=3272

題目意思：n個點m條邊的有向圖，從所有入度為0的點出發(fā)到達n，問所有可能路徑中，經(jīng)過的某條路的最大次數(shù)是多少。邊全是由標號小的到標號大的。

這道題求的是路徑的最大通過數(shù)量，感覺比較典型，挺有意思的。

思路：建兩個圖一個正圖，一個反圖。將正圖dfs一遍得到每個點到達n點的路徑數(shù)，將反圖dfs一遍得到每個點到達每個出度為0的點（奶牛的放牧地）的路徑數(shù)，對于每條邊正圖上的終點路徑數(shù)*反圖上起點的路徑數(shù)的最大值就是答案。

代碼：

1 //Author: xiaowuga 2 #include <iostream> 3 #include <algorithm> 4 #include <set> 5 #include <vector> 6 #include <queue> 7 #include <cmath> 8 #include <cstring> 9 #include <cstdio> 10 #include <ctime> 11 #include <map> 12 #include <bitset> 13 #include <cctype> 14 #define maxx INT_MAX 15 #define minn INT_MIN 16 #define inf 0x3f3f3f3f 17 #define mem(s,ch) memset(s,ch,sizeof(s)) 18 #define nc cout<<"nc"<<endl 19 #define sp " " 20 const long long N=5*10000+20; 21 using namespace std; 22 typedef long long LL; 23 typedef int II; 24 struct eage{ 25 LL x,y; 26 }E[N]; 27 vector<LL>p[5000+10]; 28 vector<LL>q[5000+10]; 29 LL n,m; 30 LL ansp[5000+10]; 31 LL ansq[5000+10]; 32 LL in[5000+10]; 33 LL vis[5000+10]; 34 void init(){ 35 for(II i=0;i<=n;i++){ 36 p[i].clear();q[i].clear(); 37 in[i]=vis[i]=ansq[i]=ansp[i]=0; 38 } 39 } 40 LL dfsp(LL x){//正圖 41 if(vis[x]) return ansp[x]; 42 vis[x]=1; 43 if(x==n) return ansp[x]=1; 44 for(LL i=0;i<p[x].size();i++){ 45 LL t=p[x][i]; 46 ansp[x]+=dfsp(t); 47 } 48 return ansp[x]; 49 } 50 LL dfsq(LL x){//反圖 51 if(vis[x]) return ansq[x]; 52 vis[x]=1; 53 if(!in[x]) return ansq[x]=1; 54 for(LL i=0;i<q[x].size();i++){ 55 LL t=q[x][i]; 56 ansq[x]+=dfsq(t); 57 } 58 return ansq[x]; 59 } 60 void solve(){ 61 for(LL i=1;i<=n;i++){ 62 if(!in[i]) dfsp(i); 63 } 64 mem(vis,0); 65 dfsq(n); 66 LL ans=minn; 67 for(LL i=0;i<m;i++){ 68 LL x=E[i].x; 69 LL y=E[i].y; 70 ans=max(ans,ansp[y]*ansq[x]); 71 } 72 cout<<ans<<endl; 73 } 74 int main() { 75 ios::sync_with_stdio(false);cin.tie(0); 76 while(cin>>n>>m){ 77 init(); 78 for(II i=0;i<m;i++){ 79 cin>>E[i].x>>E[i].y; 80 p[E[i].x].push_back(E[i].y);//正圖 81 q[E[i].y].push_back(E[i].x);//反圖 82 in[E[i].y]++; 83 } 84 solve(); 85 } 86 return 0; 87 } View Code

?

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

總結(jié)

以上是生活随笔為你收集整理的POJ3272 Cow Traffic的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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