http://www.lydsy.com/JudgeOnline/problem.php?id=1638

RunID
User
Problem
Result
Memory
Time
Language
Code_Length
Submit_Time
371552
Accepted
1684 kb
32 ms
985 B
2013-03-19 15:20:26

 

描述

给定一个有向无环图，起点为所有入度为0的点，终点为N。题目大意

计算所有路径通过某条边的最大次数。

样例:

 1   4
  \ / \
   3   6 -- 7
  / \ /
 2   5
通向奶牛宿舍的所有路径: 
1 3 4 6 7
1 3 5 6 7
2 3 4 6 7
2 3 5 6 7
所以 6-->7 的经过次数最多，为4.
 

题解

把所有起点入队，正向BFS，求出所有起点到每个点的路径数f[i]；

把终点入队，反向BFS，求出终点到每个点的路径数g[i]；

ans=max{g[u]*f[v]} | (u,v)∈E；

 

#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5001,M=50001;
int v[M],next[M],head[N],in[N],k;
int x[M],y[M],f[N],g[N],*d,q[N],n,m;
void add(int x,int y)
{
	v[++k]=y;next[k]=head[x];head[x]=k;
	in[y]++;
}
void bfs(int d[])
{
	memset(d,0,sizeof(d));
	int l=0,r=0;
	for(int i=1;i<=n;i++)
		if(!in[i])	q[++r]=i,d[i]=1;
	while(++l<=r)
		for(int i=head[q[l]];i;i=next[i])
		{
			d[v[i]]+=d[q[l]];
			if(!--in[v[i]])	q[++r]=v[i];
		}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		if(x>y)	swap(x[i],y[i]);
		add(x[i],y[i]);
	}
	bfs(f);
	memset(in,0,sizeof(in));
	memset(head,0,sizeof(head));k=0;
	for(int i=0;i<m;i++)	add(y[i],x[i]);
	bfs(g);
	int ans=0;
	for(int i=0;i<m;i++)
		ans=max(ans,f[x[i]]*g[y[i]]);
	printf("%d\n",ans);
}