题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1638
题意：
给你一个有向图，n个点，m条有向边。
对于所有从入度为0的点到n的路径，找出被经过次数最多的一条边，输出这个次数。
题解：
edge为原边，redge为反向边。
cnt[i]表示从入度为0的点到i的路径数。
rev[i]表示从i到n的路径数。
两遍记忆化搜索，处理出数组cnt和rev。
每条边(a,b)被经过的次数 = cnt[a]*rev[b]
扫一遍取最大，即为答案。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 5005 using namespace std; int n,m;
int ans=;
int cnt[MAX_N];
int rev[MAX_N];
vector<int> edge[MAX_N];
vector<int> redge[MAX_N]; void read()
{
cin>>n>>m;
int a,b;
for(int i=;i<m;i++)
{
cin>>a>>b;
edge[a].push_back(b);
redge[b].push_back(a);
}
} void dfs(int now,int *cnt,const vector<int> *edge)
{
if(cnt[now]!=-) return;
if(!edge[now].size())
{
cnt[now]=;
return;
}
cnt[now]=;
for(int i=;i<edge[now].size();i++)
{
int temp=edge[now][i];
dfs(temp,cnt,edge);
cnt[now]+=cnt[temp];
}
} void solve()
{
memset(cnt,-,sizeof(cnt));
memset(rev,-,sizeof(rev));
for(int i=;i<=n;i++)
{
if(rev[i]==-) dfs(i,rev,edge);
}
dfs(n,cnt,redge);
for(int i=;i<=n;i++)
{
for(int j=;j<edge[i].size();j++)
{
int temp=edge[i][j];
ans=max(ans,cnt[i]*rev[temp]);
}
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}