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;
}