记录编号	429449	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-07-27 11:00:02	内存使用	0.50 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int maxn=5010;

queue<int>q;
vector<int> G[maxn];
vector<int> P[maxn];

int n,m,x,y;
int f[maxn],g[maxn];
int rd[maxn],cd[maxn];
long long ans;

int fread(){
	int a=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	a*=f;
	return a;
}

inline void init(){
	//scanf("%d %d",&n,&m);
	n=fread(),m=fread();
	for(int i=1;i<=m;i++){
		//scanf("%d %d",&x,&y);
		x=fread(),y=fread();
		G[x].push_back(y);
		P[y].push_back(x);
		rd[y]++;
		cd[x]++;
	}
}

inline void work(){
	for(int i=1;i<=n;i++){
		if(!rd[i]){
			f[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			rd[v]--;
			f[v]+=f[u];
			if(!rd[v])
				q.push(v);
		}
	}
	g[n]=1; q.push(n);
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=0;i<P[u].size();i++){
			int v=P[u][i];
			cd[v]--;
			g[v]+=g[u];
			if(!cd[v])
				q.push(v);
		}
	}
}

inline void prin(){
	ans=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<G[i].size();j++)
			if(1ll*f[i]*g[G[i][j]]>ans)
				ans=f[i]*g[G[i][j]];
	cout<<ans<<endl;
}

int main(){
	freopen("cowtraffic.in","r",stdin);
	freopen("cowtraffic.out","w",stdout);
	init();
	work();
	prin();
    return 0;
}
/*
7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7
*/