「Bzoj 1638」「Usaco2007 Mar」Cow Traffic 奶牛交通 (树形DP+乘法原理)

BZOJ 1638
Luogu 2883
from: USACO 2007 Mar Sliver(USACO刷题第14题)

一开始只能想到暴力做法，看了题解才知道怎么做
首先，对于一条边$(a,b)$, 设入度为0的节点为$w$, $path(x, y)$为$x -> y$的路径条数
根据乘法原理，经过该边次数为
$$path(w, a) * path(b, n)$$
这样我们可以分别求出$path(w, a), path(b, n)$，$path(w, a)$即$g$使用反图$RG$用DP求解，$path(b, n)$即$f$使用原图$G$用DP求解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 5000 + 5, MAXM = 50000 + 5;

vector<int> G[MAXN], RG[MAXN];
int n, m, a[MAXM], b[MAXM], f[MAXN], g[MAXN];

void dfs1(int u) {
    if (!G[u].size()) {f[u] = 1; return ;}
    for (int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if (!f[v]) dfs1(v);
        f[u] += f[v];
    }
}
void dfs2(int u) {
    if (!RG[u].size()) {g[u] = 1; return ;}
    for (int i=0;i<RG[u].size();i++) {
        int v = RG[u][i];
        if (!g[v]) dfs2(v);
        g[u] += g[v];
    }
}
void clean() {
    for (int i=0;i<=n;i++) G[i].clear(), RG[i].clear(), f[i] = g[i] = 0;
}
void init() {
    clean();
    for (int i=1;i<=m;i++) {
        scanf("%d%d", &a[i], &b[i]);
        G[a[i]].push_back(b[i]), RG[b[i]].push_back(a[i]);
    }
}
void solve() {
    for (int i=1;i<=n;i++) if (!f[i]) dfs1(i); 
    dfs2(n);
    int ans = 0;
    for (int i=1;i<=m;i++) ans = max(ans, g[a[i]]*f[b[i]]);
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &m)==2) init(), solve();
    return 0;
}