Algoogle

Algorithm for Programming Contest

PKU 3272 Cow Traffic

Category: PKU Tag: dp

Cow Traffic

問題概要


始点(他の点から入ってくる辺がない点)からN番目の点までパス全てを考える時,
それらのパスに含まれるある辺について, その辺を含むパスの数の最大値を出す.

解法


各点からN番目の点までのパスの数を出しておく.(辺を逆に張ってN番目の点から各点までのパスの数を出せばいい)
あとは始点から各点までのパスの総数を出していき, 各辺を見るときに
辺の出る点までのパスの総数と, 辺の入る点からN番目の点までのパスの総数をかけ合わせればいい.

コード


(3272.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int N, M;
vector<int> E[5010];
vector<int> RE[5010];
int dp[5010];
int dp2[5010];

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; i++){
        int a, b; scanf("%d%d", &a, &b);
        a--; b--;
        E[a].push_back(b);
        RE[b].push_back(a);
    }

    int ans = 0;
    dp[N-1] = 1;
    for(int i = N-1; i >= 0; i--)
        for(int j = 0; j < RE[i].size(); j++)
            dp[RE[i][j]] += dp[i];

    for(int i = 0; i < N; i++){
        if(!dp2[i]) dp2[i] = 1;
        for(int j = 0; j < E[i].size(); j++){
            dp2[E[i][j]] += dp2[i];
            ans = max(ans, dp2[i] * dp[E[i][j]]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Comments