2832458_ac_0ms_468k.cpp

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

#include <stdio.h>
#include <math.h>
#include <string.h>
#define INF 2100000000
#define MaxV 201

int n, p, m;
int q[201];
int ans;
int map[200][200];
struct node
{
	int a[11];
};

node in[51], out[51];

int con[200][200];
int num;

int bfs()
{
	int a, b;
	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 = INF+1;
	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;
			if(p!=m-1&&pre[p]!=0&&p-pre[p]!=n)
			{
				a = pre[p];
				b = p;
				if(a>n)
					a -= n;
				if(b>n)
					b -= n;
			//	if(con[b][a])
				//	goto con;
				if(con[a][b]==0)
				{
					con[a][b] = C;
					num++;
				}
				else
					con[a][b] += C;
			}
con:
			;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

int main()
{
	int i, j, k;
	int a, b;
	int flag;

	scanf("%d%d",&p,&n);
	ans = num = 0;
	memset(map,0,sizeof(map));
	for(i = 0; i < n; i++)
	{
		scanf("%d",&q[i]);
		for(j = 0; j < p; j++)
			scanf("%d",&in[i].a[j]);
		for(j = 0; j < p; j++)
			scanf("%d",&out[i].a[j]);
	}
	for(i = 0; i < n; i++)
	{
		flag = 1;
		for(j = 0; j < p; j++)
			if(in[i].a[j]==1)
			{
				flag = 0;
				break;
			}
		map[0][i+1] = flag*INF;
		flag = 1;
		for(j = 0; j < p; j++)
			if(out[i].a[j]==0)
			{
				flag = 0;
				break;
			}
		map[i+n+1][2*n+1] = flag*INF;
	}
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			if(i==j)
				continue;
			flag = 1;
			for(k = 0; k < p; k++)
			{
				a = out[i].a[k];
				b = in[j].a[k];
				if(b==2)
					continue;
				if(b!=a)
				{
					flag = 0;
					break;
				}
			}
			map[i+n+1][j+1] = flag*q[i];
		}
	for(i = 1; i <= n; i++)
		map[i][i+n] = q[i-1];
	m = 2*n+2;
	memset(con,0,sizeof(con));
	while(bfs());
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
		{
			if(i!=j&&con[i][j]&&con[i][j]==con[j][i])
			{
				num-=2;
				con[i][j] = con[j][i] = 0;
			}
		}
	printf("%d %d\n",ans,num);
	int tt = 0;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			if(con[i][j])
			{
				tt++;
				if(i==j)
				{
					while(1)
						puts("ASDASDASDASD");
				}
				printf("%d %d %d\n",i,j,con[i][j]);
			}
		if(tt!=num)
			while(1);
	return 0;
}