poj 3272図上dp(ある辺を通る最大経路数)

問題:n個の点とm個のエッジを有する有向無ループ図を与える.出度0の点はn点のみであることが知られている.すべての入度が0の点からnに到着し、すべての可能な経路の中で、ある道を通る最大回数を聞く.
問題解:トポロジーソートの順序で順方向に進み、ある点に到達した経路の総数dp配列を記録する.nから逆行し,ある点から終点までの合計数num配列を記録する.2パス目のスキャンでは,各エッジを列挙し,そのエッジが2点に対応して記録された2つの情報の積の最大値を求める.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s));
#define N 5005
int n,m;
struct edge{
    int y,next,flag;
}e[50005<<1];
int first[N],d[N],g[N],top,dp[N],num[N];
void add(int x,int y,int flag){
    e[top].y = y;
    e[top].flag = flag;
    e[top].next = first[x];
    first[x] = top++;
}
int main(){
    int i,a,b,now,res=0;
    queue<int> q;
    clr(first,-1);
    clr(dp, 0);
    clr(d,0);
    clr(g, 0);
    clr(num, 0);
    top = 0;
    scanf("%d %d",&n,&m);
    for(i = 1;i<=m;i++){
        scanf("%d %d",&a,&b);
        add(a,b,1);
        add(b,a,2);
        d[b]++;
        g[a]++;
    }
    for(i = 1;i<=n;i++)
        if(!d[i]){
            q.push(i);
            dp[i] = 1;
        }
    while(!q.empty()){
        now = q.front();
        q.pop();
        for(i = first[now];i!=-1;i=e[i].next){
            if(e[i].flag == 2)
                continue;
            dp[e[i].y] += dp[now];
            d[e[i].y]--;
            if(!d[e[i].y])
                q.push(e[i].y);
        }
    }
    num[n] = 1;
    q.push(n);
    while(!q.empty()){
        now = q.front();
        q.pop();
        for(i = first[now];i!=-1;i=e[i].next){
            if(e[i].flag == 1)
                continue;
            num[e[i].y] += num[now];
            res = max(res,num[now]*dp[e[i].y]);
            g[e[i].y]--;
            if(!g[e[i].y])
                q.push(e[i].y);
        }
    }
    printf("%d
",res);
    return 0;
}