记录编号	452909	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-09-20 16:53:06	内存使用	1.57 MiB

#include<bits/stdc++.h>
#define v e[i].to
using namespace std;
int n,m,fi[5005],tot,f1[5005],f2[5005],in[5005],out[5005],tot2,head[5005];
struct edge{
	int to,next,from;
}e[50005],E[50005];
void edge_add(int x,int y){
	e[++tot].to=y;
	e[tot].from=x;
	e[tot].next=fi[x];
	fi[x]=tot;
}
void Edge_add(int x,int y){
	E[++tot2].to=y;
	E[tot2].next=head[x];
	head[x]=tot2;
}
int main()
{
	freopen("cowtraffic.in","r",stdin);
	freopen("cowtraffic.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		edge_add(a,b);
		Edge_add(b,a);
		in[b]++;out[a]++;
	}
	queue<int>S;
	for(int i=1;i<=n;i++)if(!in[i])S.push(i),f1[i]=1;
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=fi[u];i;i=e[i].next){
			f1[v]+=f1[u];
			in[v]--;
			if(!in[v])S.push(v);
		}
	}
	for(int i=1;i<=n;i++)if(!out[i])S.push(i),f2[i]=1;
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=head[u];i;i=E[i].next){
			f2[E[i].to]+=f2[u];
			out[E[i].to]--;
			if(!out[E[i].to])S.push(E[i].to);
		}
	}
	int ma=-1;
	for(int i=1;i<=m;i++){
		ma=max(ma,f1[e[i].from]*f2[e[i].to]);
	}
	cout<<ma;
	return 0;
}