设f[u]为从度数0到u的路径条数，f2[u]为从u到n的路径条数。
ans=max{f[x[i]]*f2[y[i]]}(1<=i<=m)。
#include#include #include using namespace std;#define N 5001typedef long long ll;#define M 50001int 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;}