首先,对于一条边(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