2322806_ac_214ms_2028k.cpp

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

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

int n, m;
int map[501][501];
int stack[501][501];

int bfs()
{
	int i, mark = 0;
	int f, r, p;
	int pre[501], visited[501];
	int queue[510], C, F[510];

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(F,0,sizeof(F));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = 35000;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < n; i++)
			if(map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = map[p][i];
				if(i==n-1)
				{	
					mark = 1;
					goto m1;
				}
			}
	}
	m1:;
	if(mark)
	{
		p = n-1;
		while(pre[p]!=-1)
		{
			if(F[p]<C)
				C = F[p];
			p = pre[p];
		}
		p = n-1;
		while(pre[p]!=-1)
		{
			map[pre[p]][p] -= C;
			if(map[pre[p]][p]==0)
				stack[pre[p]][p] = 1;
			map[p][pre[p]] += C;
			p = pre[p];
		}
	}
	else
	{
		int ff, rr, Queue[501];

		ff = rr = -1;
		Queue[++ff] = n-1;
		memset(visited,0,sizeof(visited));
		visited[n-1] = 1;
		while(ff!=rr)
		{
			++rr;
			p = Queue[rr];
			for(i = 0; i < n-1; i++)
			{
				if(map[i][p]&&!visited[i])
				{
					visited[i] = 1;
					Queue[++ff] = i;
				}
			}
		}
		int j, ans = 0;
		for(i = 0; i <= f; i++)
			for(j = 0; j <= ff; j++)
			{
				if(stack[queue[i]][Queue[j]])
					ans++;
			}
		printf("%d\n",ans);
	}
	return mark;
}

int main()
{
	int i;
	int st, ed, w;

	scanf("%d%d",&n,&m);
	memset(map,0,sizeof(map));
	memset(stack,0,sizeof(stack));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&st,&ed,&w);
		map[st][ed] += w;
	}
	while(bfs());
	return 1;
}