首先,對於一條邊(a,b),原圖中入度爲0的點到a的路徑條數F,原圖中b到N的路徑條數G,那麼這條邊的經過次數爲F*G.

對於每個頂點i，我們只需求出F[i]和G[i]。

動態規劃

狀態

* F[i] 爲入度爲0的點到i的路徑條數
* G[i] 爲i到N的路徑條數 

狀態轉移方程

* F[i]=Sum{ F[j] } 存在邊(j,i)
* G[i]=Sum{ G[j] } 存在邊(i,j) 

邊界條件

* F[k]=1 k爲入度爲0的點
* G[N]=1 

目標結果

* Ans=Max{ F[a]*G[b] } 存在邊(a,b) 

注意：圖中可以有重邊。而且由於N很大，而M較小，建議使用鄰接表存儲。

#include <iostream>
#define MAXN 5001
#define MAXM 50001
using namespace std;

class list
{
public:
    list *next;
    int p;
    list(int tp)
    {
        p=tp;
        next=0;
    }
};

class tadjl
{
public:
    list *first,*last;
    void ins(int p)
    {
        if (first)
            last=last->next=new list(p);
        else
            first=last=new list(p);
    }
    tadjl()
    {
        first=last=0;
    }
};

int N,M,Ans;
int F[MAXN],G[MAXN];
tadjl adjl[MAXN],rdjl[MAXN];

void init()
{
    int i,a,b;
    freopen("cowtraffic.in","r",stdin);
    freopen("cowtraffic.out","w",stdout);
    cin >> N >> M;
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        rdjl[a].ins(b);
        adjl[b].ins(a);
    }
}

int dynamic1(int i)
{
    int j,A=0;
    list *k;
    if (!adjl[i].first)
        return 1;
    for (k=adjl[i].first;k;k=k->next)
    {
        j=k->p;
        if (F[j]==0)
            F[j]=dynamic1(j);
        A+=F[j];
    }
    return A;
}

int dynamic2(int i)
{
    int j,A=0;
    list *k;
    if (!rdjl[i].first)
        return 1;
    for (k=rdjl[i].first;k;k=k->next)
    {
        j=k->p;
        if (G[j]==0)
            G[j]=dynamic2(j);
        A+=G[j];
    }
    return A;
}

void solve()
{
    int i,j,V;
    list *k;
    F[N]=dynamic1(N);
    G[1]=dynamic2(1);
    for (i=1;i<N;i++)
    {
        for (k=rdjl[i].first;k;k=k->next)
        {
            j=k->p;
            V=F[i]*G[j];
            if (V>Ans)
                Ans=V;
        }
    }
}

int main()
{
    init();
    solve();
    cout << Ans << endl;
    return 0;
}

<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_03_S/Cow_Traffic/%E9%A2%98%E8%A7%A3">奶牛交通</a>

譯: zqzas


農場中,由於奶牛數量的迅速增長,通往奶牛宿舍的道路也出現了嚴重的交通擁堵問題.FJ打算找出最忙碌的道路來重點整治.

這個牧區包括一個由M (1 ≤ M ≤ 50,000)條單行道路(有向)組成的網絡,以及 N (1 ≤ N ≤ 5,000)個交叉路口(編號爲1..N),每一條道路連接兩個不同的交叉路口.奶牛宿舍位於第N個路口.每一條道路都由編號較小的路口通向編號較大的路口.這樣就可以避免網絡中出現環.顯而易見,所有道路都通向奶牛宿舍.而兩個交叉路口可能由不止一條邊連接.

在準備睡覺的時候,所有奶牛都從他們各自所在的交叉路口走向奶牛宿舍,奶牛隻會在入度爲0的路口,且所有入度爲0的路口都會有奶牛.

幫助FJ找出最忙碌的道路,即計算所有路徑中通過某條道路的最大次數.答案保證可以用32位整數存儲.


輸入格式:

    * 第一行:兩個用空格隔開的整數:N,M.
    * 第二行到第M+1行:每行兩個用空格隔開的整數ai,bi,表示一條道路從ai到bi. 


輸出格式:

    * 第一行: 一個整數,表示所有路徑中通過某條道路的最大次數. 

樣例輸入:

7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7

樣例輸出

4

樣例說明:

    1   4
      / 
      3   6 -- 7
     /  /
    2   5

通向奶牛宿舍的所有路徑:

    1 3 4 6 7
    1 3 5 6 7
    2 3 4 6 7
    2 3 5 6 7