2821646_ac_640ms_116k.c

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxV 105

int n, np, nc, m;
int ans, map[MaxV][MaxV];

int input()
{
	int i, j;
	int st, ed;
	int w;
	char tmp[20];

	if(scanf("%d%d%d%d",&n,&np,&nc,&m)!=4)
		return 0;
	ans = 0;
	memset(map,0,sizeof(map));
	for(i = 0; i < m; i++)
	{
		scanf("%s",tmp);
		for(j = 0; tmp[j]!='\0'; j++)
		{
			if(tmp[j]=='(')
				st = atoi(&tmp[j+1]);
			if(tmp[j]==',')
				ed = atoi(&tmp[j+1]);
			if(tmp[j]==')')
			{
				w = atoi(&tmp[j+1]);
				break;
			}
		}
		st++;ed++;
		if(st!=ed)
			map[st][ed] += w;
	}
	for(i = 0; i < np; i++)
	{
		scanf("%s",tmp);
		for(j = 0; tmp[j]!='\0'; j++)
		{
			if(tmp[j]=='(')
				st = atoi(&tmp[j+1]);
			if(tmp[j]==')')
			{
				w = atoi(&tmp[j+1]);
				break;
			}
		}
		st++;
		map[0][st] += w;
	}
	for(i = 0; i < nc; i++)
	{
		scanf("%s",tmp);
		for(j = 0; tmp[j]!='\0'; j++)
		{
			if(tmp[j]=='(')
				ed = atoi(&tmp[j+1]);
			if(tmp[j]==')')
			{
				w = atoi(&tmp[j+1]);
				break;
			}
		}
		ed++;
		map[ed][n+1] += w;
	}
	return 1;
}

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

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = 2100000000;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < n+2; 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;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

int main()
{
	while(input())
	{
		while(bfs());
		printf("%d\n",ans);
	}
	return 1;
}