3294239_tle.cpp

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

#include <stdio.h>
#include <string.h>
#define INF 2100000000

struct node
{
	int c, w, f;
}net[110][110];

struct Node
{
	int v, fa;
}best[110];

int n, s, t;
int minc;

int N, M, K;
int error;
int nk[51][51], knm[51][51][51], mk[51][51];

int init()
{
	int i, j, k;
	int num[51], app[51];

	error = 1;
	scanf("%d%d%d",&N,&M,&K);
	memset(num,0,sizeof(num));
	memset(app,0,sizeof(app));
	if(N==0&&M==0&&K==0)
		return 0;
	minc = 0;
	for(i = 1; i <= N; i++)
	{
		for(k = 1; k <= K; k++)
		{
			scanf("%d",&nk[i][k]);
			num[k] += nk[i][k];
		}
	}
	for(i = 1; i <= M; i++)
	{
		for(k = 1; k <= K; k++)
		{
			scanf("%d",&mk[i][k]);
			app[k] += mk[i][k];
		}
	}
	for(k = 1; k <= K; k++)
	{
		for(i = 1; i <= N; i++)
		{
			for(j = 1; j <= M; j++)
			{
				scanf("%d",&knm[k][i][j]);
			}
		}
	}
	for(i = 1; i <= k; i++)
		if(num[i]>app[i])
		{
			error = 0;
			break;
		}
	t = 0;s = 1+M+N;n = 1+s;
	return 1;
}

int Find_Way()
{
	int i, j;
	int quit;

	for(i = 0; i < n; i++)
		best[i].v = INF;
	best[s].v = 0;
	do
	{
		quit = 1;
		for(i = 0; i < n; i++)
		{
			if(best[i].v<INF)
			{
				for(j = 0; j < n; j++)
				{
					if(net[i][j].f<net[i][j].c&&best[i].v+net[i][j].w<best[j].v)
					{
						best[j].v = best[i].v+net[i][j].w;
						best[j].fa = i;
						quit = 0;
					}
				}
			}
		}
	}while(!quit);
	if(best[t].v<INF)
		return 1;
	return 0;
}

void Add_Way()
{
	int i, j;
	int MINC;

	MINC = -1;
	i = t;
	do
	{
		j = i;
		i = best[j].fa;
		if(MINC==-1||net[i][j].c < MINC)
		{
			MINC = net[i][j].c;
		}
	}
	while (i!=s);
	i = t;
	do
	{
		j = i;
		i = best[j].fa;
		net[i][j].f += MINC;
		net[j][i].f = -net[i][j].f;
	}
	while(i!=s);
	minc += best[t].v;
}

void get_graph(int k)
{
	int i, j;

	memset(net,0,sizeof(net));
	for(i = 1; i <= N; i++)
	{
		net[i][0].c = nk[i][k];
		net[i][0].w = net[0][i].w = 0;
	}
	for(i = 1; i <= M; i++)
	{
		for(j = 1; j <= N; j++)
			net[i+N][j].c = mk[i][k];
		net[s][i+N].c = mk[i][k];
		net[s][i+N].w = net[i+N][s].w = 0;
	}
	for(i = 1; i <= N; i++)
		for(j = 1; j <= M; j++)
		{
			net[j+N][i].w = knm[k][i][j];
			net[i][j+N].w = -knm[k][i][j];
		}
}

int main()
{
	int k;

	while(init())
	{
		if(!error)
		{
			puts("-1");
			continue;
		}
		for(k = 1; k <= K; k++)
		{
			get_graph(k);
			while(Find_Way())
				Add_Way();
		}
		printf("%d\n",minc);
	}
	return 0;
}