POJ 3272 - Cow Traffic

http://poj.org/problem?id=3272

概要

N 個のノードと M 本のエッジからなる DAG が与えられる． 入ってくるエッジが無いノードがスタート地点，番号 N のノードがゴール地点である．

スタート地点からゴール地点までの可能な経路を考えたとき，そのような経路に最も含まれているエッジは何種類の経路に含まれているかを答える．

制約

解法

スタート地点からあるノード i までの経路の数 v[i] と，あるノード j からゴール地点までの経路の数 v_rev[j] を，それぞれ BFS というか DP 的に数えておくと， ノード i, j を結ぶエッジは v[i] * v[j] 種類の経路に含まれていることになるので，これの最大値をとればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 vector<int> bfs(const vector<vector<int> >& g, vector<int>& deg)
 7 {
 8   const int N = g.size();
 9   queue<int> q;
10   vector<int> v(N, 0);
11   for (int i = 0; i < N; i++) {
12     if (deg[i] == 0) {
13       q.push(i);
14       v[i] = 1;
15     }
16   }
17   while (!q.empty()) {
18     const int n = q.front();
19     q.pop();
20     for (vector<int>::const_iterator it(g[n].begin()); it != g[n].end(); ++it) {
21       --deg[*it];
22       v[*it] += v[n];
23       if (deg[*it] == 0) {
24         q.push(*it);
25       }
26     }
27   }
28   return v;
29 }
30 
31 int main()
32 {
33   int N, M;
34   scanf("%d %d", &N, &M);
35   vector<vector<int> > g(N), g_rev(N);
36   vector<int> deg(N, 0), deg_rev(N, 0);
37   for (int i = 0; i < M; i++) {
38     int u, v;
39     scanf("%d %d", &u, &v);
40     --u;  --v;
41     g[u].push_back(v);
42     g_rev[v].push_back(u);
43     ++deg[v];
44     ++deg_rev[u];
45   }
46 
47   const vector<int> v = bfs(g, deg);
48   const vector<int> v_rev = bfs(g_rev, deg_rev);
49   int ans = 0;
50   for (int i = 0; i < N; i++) {
51     for (vector<int>::const_iterator it(g[i].begin()); it != g[i].end(); ++it) {
52       ans = max(ans, v[i] * v_rev[*it]);
53     }
54   }
55   printf("%d\n", ans);
56   return 0;
57 }
poj/3272.cc