3118059_re.c

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

#include <stdio.h>
#include <string.h>
#define MaxV 201

int din[201], dout[201];
int map[201][201];
int ans;

int bfs(int m)
{
	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 < m; i++)
			if(map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = map[p][i];
				if(i==m-1)
				{	
					mark = 1;
					goto m1;
				}
			}
	}
	m1:;
	if(mark)
	{
		p = m-1;
		while(pre[p]!=-1)
		{
			if(F[p]<C)
				C = F[p];
			p = pre[p];
		}
		p = m-1;
		while(pre[p]!=-1)
		{
			map[pre[p]][p] -= C;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

int main()
{
	int cas, err, res;
	int m, s, i;
	int a, b, c;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d%d",&m,&s);
		memset(din,0,sizeof(din));
		memset(dout,0,sizeof(dout));
		memset(map,0,sizeof(map));
		for(i = 0; i < s; i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			din[b]++;
			dout[a]++;
			if(c==0)
			{
				map[a][b] = 1;
			}
		}
		err = 0;
		for(i = 1; i <= m; i++)
		{
			if((din[i]+dout[i])%2!=0||(din[i]-dout[i])%2!=0)
			{
				err = 1;
				break;
			}
		}
		if(err==1)
		{
			puts("impossible");
			continue;
		}
		res = 0;
		for(i = 1; i <= m; i++)
		{
			if(din[i] > dout[i])
			{
				map[i][m+1] = (din[i]-dout[i])/2;
			}
			else
			{
				res += (map[0][i] = (dout[i]-din[i])/2);
			}
		}
		ans = 0;
		while(bfs(m+2));
		printf(ans==res?"possible\n":"impossible\n");
	}
	return 0;
}