记录编号	429447	评测结果	AAAAAWWWEW
题目名称	165.[USACO Mar07] 奶牛交通	最终得分	50
用户昵称	Menamovic	是否通过	未通过
代码语言	C++	运行时间	0.073 s
提交时间	2017-07-27 10:59:16	内存使用	1.19 MiB

#include<iostream>
#include<cstdio>

using namespace std;

int f[5005],g[5005];
int fr[5050],to[5050];
int head[5050],header[5050];

struct Edge
{
	int next;
	int to;
}e[50010],er[50010];

int n,m;
int cnt=0;
int ct=0;

void addedge(int from,int to)
{
	e[cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt++;
	er[ct].next=header[to];
	er[ct].to=from;
	header[to]=ct++;
}
void dfs(int x)
{
	if(!head[x])
	{
		f[x]=1;
		return ;
	}
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(!f[to])
		dfs(to);
		f[x]+=f[to];
	}
}
void dfs2(int x)
{
	if(!header[x])
	{
		g[x]=1;
		return;
	}
	for(int i=header[x];i;i=er[i].next)
	{
		int to=er[i].to;
		if(!g[to]) dfs2(to);
		g[x]+=g[to];
	}
}
int main()
{
	freopen("cowtraffic.in","r",stdin);
	freopen("cowtraffic.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&fr[i],&to[i]);
		addedge(fr[i],to[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!f[i]);
		dfs(i);
	}
	dfs2(n);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		ans=max(ans,f[to[i]]*g[fr[i]]);
	}
	printf("%d",ans);
	return 0;
}