cow traffic(dfs求边通过次数).cpp

杭电acm解题报告2001---2099.

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

int v[5100],ps[51000],ps2[51000];
int n,m;
struct node {
	int e,m;
};
vector< vector<node> > nmap;
vector< vector<node> > map;

int dfs(int pos, vector< vector<node> > & path, int path_num[51000])
{
	int i,j = 0,k = 0;
	node edge;

	if (v[pos] >= 0) {//到达该节点前所有路径数
		return v[pos];
	}
	if (path[pos].size() == 0) {//到达叶节点，路径为 1
		return 1;
	}
	for (i=path[pos].size()-1;i>=0;i--) {
		edge = path[pos][i];//遍历每条边
		j = dfs(edge.e, path, path_num);
		path_num[edge.m] += j;//计算通过该边到达叶节点的路径数
		k += path_num[edge.m];//计算到达该节点前所有路径数
	}
	v[pos] = k;//返回该节点所有路径数
	return k;
}

int main()
{
	int i,j,ans;
	int x,y;
	node edge;

	while (scanf("%d %d",&n,&m)==2) {
		nmap.resize(n+10);
		for (i=0;i<=n;i++) {
			nmap[i].clear();
		}
		map.resize(n+10);
		for (i=0;i<=n;i++) {
			map[i].clear();
		}

		for (i=0;i<m;i++) {
			scanf("%d %d",&x,&y);
			edge.e = x;
			edge.m = i;
			nmap[y].push_back(edge);//逆图
			edge.e = y;
			map[x].push_back(edge);//原图
		}
		
		if (nmap[n].size() == 0) {
			printf("0\n");
		}
		else {
			ans = 0;
			memset(v, -1,sizeof(v));
			memset(ps,0,sizeof(ps));
			dfs(n, nmap, ps);

			memset(v, -1,sizeof(v));
			memset(ps2,0,sizeof(ps2));
			for (i=1;i<n;i++) {
				dfs(i, map, ps2);
			}

			for (i=0;i<m;i++) {
				if (ps[i] * ps2[i] > ans) {//经过该边连通首尾的所有路径数 取最大值
					ans = ps[i] * ps2[i];
				}
			}
			printf("%d\n",ans);
		}
	}
}