3272 Cow Traffic

PKU

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

概要

DAGが与えられる。
初期地点が入ってくる辺のない点、最終地点が一番番号の大きな点となるようなパスをすべて考えて
そのようなパスにもっとも多く入っている辺は、いくつのパスに含まれるか求める問題。

方針

ある点から最終地点までのパスの数と、ある点までのパスの数とをあらかじめ深さ優先探索して求めておく。
すべての辺に対して、(辺の始点までのパスの数)*(辺の終点から最終地点までのパスの数)の最大値が答えになる。
DFSにO(N)、最大値を求めるのにO(M)かかるので全体でO(N+M)になる。

ソース

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

struct Edge{
  int s,t;
  Edge(int s,int t) : s(s), t(t) {;}
};

int dfs(vector<vector<Edge> > &g,int p,vector<int> &paths) {
  if(paths[p] != 0) return paths[p];
  if(g[p].empty()) {
    return paths[p] = 1;
  }

  int m = 0,i;
  rep(i,g[p].size()) {
    m += dfs(g,g[p][i].t,paths);
  }

  return paths[p] = m;
}

int main() {
  int n,m,i,j,k;
  scanf("%d %d", &n, &m);
  vector<vector<Edge> > in(n), out(n);

  rep(i,m) {
    scanf("%d %d", &j, &k);
    j--,k--;
    out[j].push_back(Edge(j,k));
    in[k].push_back(Edge(k,j));
  }

  vector<int> paths(n,0),bpath(n,0);
  dfs(in,n-1,paths);
  rep(i,n) if(in[i].empty()) dfs(out,i,bpath);

  int ans = 0;
  rep(i,n) {
    rep(j,out[i].size()) {
      ans = max(ans, paths[i]*bpath[out[i][j].t]);
    }
  }

  printf("%d\n", ans);
}