记录编号	132342	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-10-25 19:57:42	内存使用	1.13 MiB

#include<cstdio>
using namespace std;

struct dx{
	int to,next;
};
dx jb[50001],lxx[50001];
int last[5001];
int nexus[5001];

int n,m;
int maxx;
int r[5001],c[5001];

int main()
{
    freopen("cowtraffic.in","r",stdin);
    freopen("cowtraffic.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
  		int x,y;
  		scanf("%d%d",&x,&y);
  		if(x>y)
  		{
			x=x^y;
			y=x^y;
			x=x^y;
  		}
  		jb[i].to=y;
  		jb[i].next=last[x];
  		last[x]=i;
  		
  		lxx[i].to=x;
  		lxx[i].next=nexus[y];
  		nexus[y]=i;
	}
	c[n]=1;
	for(int i=1;i<=n;i++)
	{
		if(!nexus[i]) r[i]=1;
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=last[i];j;j=jb[j].next)
			r[jb[j].to]+=r[i];
	}
	
	for(int i=n;i>=1;i--)
	{
		for(int j=nexus[i];j;j=lxx[j].next)
			c[lxx[j].to]+=c[i];
	}
	
	for(int i=1;i<=n;i++)
	{
        for(int j=last[i];j;j=jb[j].next)
        {
			if(r[i]*c[jb[j].to]>maxx) maxx=r[i]*c[jb[j].to];
		}
	}
	printf("%d\n",maxx);
    return 0;
}