2359333_mle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n, m;
int din[5001], dout[5001];
int map[5001][5001], Map[5001][5001];
struct node
{
	int ans;
	int x, y;
}Edge[50001];
int out[5001];
int in[5001];
int queue[5001];
int Cal(int v)
{
	int i, tmp = 0;

	for(i = 1; i <= map[v][0]; i++)
		tmp += out[map[v][i]];
	return tmp;
}

void bfs()
{
	
	int f = -1,r = -1, t, i;

	queue[++f] = n-1;
	while(f!=r)
	{
		++r;
		t = queue[r];
		for(i = 1; i <= Map[t][0]; i++)
		{
			out[Map[t][i]] = Cal(Map[t][i]);
			dout[Map[t][i]]--;
			if(!dout[Map[t][i]])
				queue[++f] = Map[t][i]; 
		}
	}
	
}

int cal(int v)
{
	int i, tmp = 0;

	for(i = 1; i <= Map[v][0]; i++)
		tmp += in[Map[v][i]];
	return tmp;
}

void Bfs()
{
	int f, r, t, i;

	f = r = -1;
	memset(in,0,sizeof(in));
	for(i = 0; i < n; i++)
		if(!din[i])
			queue[++f] = i,in[i] = 1;
	while(f!=r)
	{
		++r;
		t = queue[r];
		for(i = 1; i <= map[t][0]; i++)
		{
			in[map[t][i]] = cal(map[t][i]);
			din[map[t][i]]--;
			if(!din[map[t][i]])
				queue[++f] = map[t][i];
		}
	}
}

int main()
{
	int i, a, b;

	scanf("%d%d",&n,&m);
	memset(din,0,sizeof(din));
	memset(map,0,sizeof(map));
	memset(Map,0,sizeof(Map));
	memset(dout,0,sizeof(dout));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&a,&b);
		a--,b--;
		Edge[i].x = a;Edge[i].y = b;
		dout[a]++;din[b]++;
		map[a][++map[a][0]] = b;
		Map[b][++Map[b][0]] = a;
	}
	memset(out,0,sizeof(out));
	out[n-1] = 1;
	bfs();
	Bfs();
	int max = -1;
	for(i = 0; i < m; i++)
	{
		if(in[Edge[i].x]*out[Edge[i].y]>max)
			max = in[Edge[i].x]*out[Edge[i].y];
	}
	printf("%d\n",max);
	return 1;
}