PKU 3272 Cow Traffic
問題概要
N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える.
それらのなかに最も多く含まれている辺の、含まれている回数を求めよ
辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの総数)ということに気づけば終わり。各頂点からのパスの総数はDAGなのでdpですぐ求まる。
始点が複数個あって邪魔なので新たな始点の頂点0を用意してそこから各始点に辺張ってます。
まぁ7で妥当なところかなぁと思います
#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define pb push_back vector<int> g[5050],rev[5050]; int dp[5050],dp2[5050],e[5050]; int N,M; int main() { scanf("%d %d",&N,&M); for(int i=0;i<M;i++) { int a,b; scanf("%d %d",&a,&b); e[b]++; g[a].pb(b); rev[b].pb(a); } for(int i=1;i<=N;i++)if(e[i]==0) { g[0].pb(i); rev[i].pb(0); } dp[0]=1; for(int i=1;i<=N;i++) { for(int j=0;j<rev[i].size();j++)dp[i]+=dp[rev[i][j]]; } dp2[N]=1; for(int i=N-1;i>=0;i--) { for(int j=0;j<g[i].size();j++)dp2[i]+=dp2[g[i][j]]; } int ans = 0; for(int i=1;i<=N;i++) { for(int j=0;j<g[i].size();j++)ans = max(ans,dp[i]*dp2[g[i][j]]); } printf("%d\n",ans); return 0; }