POJ 3272 Cow Traffic

問題の意味がなかなかわからなかった

問題概要

ノード数nのDAGが与えられる。入力次数が0のノードからnへのパスを全て列挙する。各辺ごとにいくつのパスに含まれているかを数えたとき、最大のパス数はいくつか。

解法

辺i -> jを含むパス数は、(入力次数0のノード -> iのパス数) * (j -> nのパス数)で求められる
前者は元のグラフを逆辺にしたグラフ上でdp, 後者は元のグラフ上でdpして求める

ソースコード

int dfs(int v, const vector<vector<int> >& g, int* dp)
{
    if (dp[v] != -1)
	return dp[v];

    int res = 0;
    rep(i, g[v].size())
	res += dfs(g[v][i], g, dp);
    return dp[v] = res;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<int> > g(n), rg(n);
    while (m--)
    {
	int a, b;
	scanf("%d%d", &a, &b);
	--a, --b;
	g[a].pb(b);
	rg[b].pb(a);
    }

    int dp[5252], rdp[5252];
    CL(dp, -1);
    CL(rdp, -1);

    dp[n - 1] = 1;
    rep(i, n - 1)
	if (rg[i].empty())
	    rdp[i] = 1;    // 0 indegree in original graph

    int res = -1;
    rep(i, n) rep(j, g[i].size())
    {
	int u = i, v = g[i][j];
	int paths = dfs(u, rg, rdp) * dfs(v, g, dp);
	chmax(res, paths);
    }
    printf("%d\n", res);
}