Bzoj 1638(树形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求解

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
------ 本文结束 ------