BZOJ 1638 [Usaco2007 Mar]Cow Traffic 奶牛交通:记忆化搜索【图中边的经过次数】

时间:2023-03-09 18:10:12
BZOJ 1638 [Usaco2007 Mar]Cow Traffic 奶牛交通:记忆化搜索【图中边的经过次数】

题目链接: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();
}