记录编号	549047	评测结果	AAAAAAAAAA
题目名称	165.[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2020-02-05 15:54:20	内存使用	13.93 MiB

#include <iostream>
#include <vector>
#include <cstdio>
#define MAX(a,b) (a > b)? a : b

using namespace std;

int n,m;
vector<int> Edeg[5001];
vector<int> Odeg[5001];
int come[5001],leave[5001];

int main()
{
    freopen ("cowtraffic.in","r",stdin);
    freopen ("cowtraffic.out","w",stdout);
    cin >> n >> m;
    leave[n] = 1;
    for(int i = 0; i < m;i++)
    {
        int a,b;
        cin >> a >> b;
        Odeg[a].push_back(b);
        Edeg[b].push_back(a);
    }
    for(int i = 1;i <= n;i++)
    {
        if(Edeg[i].size() == 0)
        {
            come[i] = 1;
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j < Odeg[i].size();j++)
        {
            come[Odeg[i][j]] += come[i];
        }
    }
    for(int i = n;i >= 1;i--)
    {
        for(int j = 0;j < Edeg[i].size();j++)
        {
            leave[Edeg[i][j]] += leave[i];
        }
    }
    int answer = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j < Odeg[i].size();j++)
        {
            answer = MAX(come[i] * leave[Odeg[i][j]],answer);
        }
    }
    cout << answer;
    return 0;
}