【动态规划】bzoj1638 [Usaco2007 Mar]Cow Traffic 奶牛交通

设f[u]为从度数0到u的路径条数，f2[u]为从u到n的路径条数。

ans=max{f[x[i]]*f2[y[i]]}(1<=i<=m)。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define N 5001

typedef long long ll;

#define M 50001

int e,v[M],first[N],next[M];

void AddEdge(int U,int V)

{

	v[++e]=V;

	next[e]=first[U];

	first[U]=e;

}

ll f[N],f2[N];

int ru[N],m,n;

int x[M],y[M];

ll ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;++i)

	  {

	  	scanf("%d%d",&x[i],&y[i]);

	  	++ru[y[i]];

		AddEdge(y[i],x[i]);

	  }

	for(int i=1;i<=n;++i)

	  if(!ru[i])

	    f[i]=1;

	for(int i=1;i<=n;++i)

	  for(int j=first[i];j;j=next[j])

	    f[i]+=f[v[j]];

	e=0;

	memset(first+1,0,sizeof(int)*n);

	for(int i=1;i<=m;++i) AddEdge(x[i],y[i]);

	f2[n]=1;

	for(int i=n;i;--i)

	  for(int j=first[i];j;j=next[j])

	    f2[i]+=f2[v[j]];

	for(int i=1;i<=m;++i) ans=max(ans,f[x[i]]*f2[y[i]]);

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

	return 0;

}