2850025_ac_2046ms_1088k.c

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

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

int n;
int edge[301][301];
int Map[301][301], link[301];
int vx[301], vy[301];
int N, M, K;
int error, pp;
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);
	if(N==0&&M==0&&K==0)
		return 0;
	memset(num,0,sizeof(num));
	memset(app,0,sizeof(app));
	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;
		}
	return 1;
}

void get_graph(int k)
{
	int i, j;
	int ti, tj;
	int ii, jj;

	ii = 0;
	pp = 0;
	memset(edge,0,sizeof(edge));
	for(i = 1; i <= N; i++)
	{
		for(ti = 0; ti < nk[i][k]; ti++)
		{
			jj = 0;
			for(j = 1; j <= M; j++)
			{
				for(tj = 0; tj < mk[j][k]; tj++)
				{
					edge[ii][jj++] = knm[k][i][j];
				}
			}
			ii++;
		}
	}
	for(i = ii; i < jj; i++)
	{
		for(j = 0; j < jj; j++)
			edge[i][j] = 1000;
		pp += 1000;
	}
	n = jj;
}

int dfs(int v)
{
	int i, t;

	for(i = 0; i < n; i++)
	{
		if(Map[v][i]&&!vy[i])
		{
			vy[i] = 1;
			t = link[i];
			link[i] = v;
			if(t==-1||dfs(t))
				return 1;
			link[i] = t;
			vx[t] = 1;
		}
	}
	return 0;
}

void KM()
{
	int i, j, live, min, t;
	int lx[301], ly[301];
	int perfect;

	for(i = 0; i < n; i++)
	{
		lx[i] = 0;
		ly[i] = INF;
		for(j = 0; j < n; j++)
			if(edge[j][i]<ly[i])
				ly[i] = edge[j][i];
	}
	perfect = 0;
	while(!perfect)
	{
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(lx[i]+ly[j]==edge[i][j])
					Map[i][j] = 1;
				else
					Map[i][j] = 0;
			}
		}
		live = 0;
		memset(link,-1,sizeof(link));
		for(i = 0; i < n; i++)
		{
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			if(dfs(i))
				live++;
			else
			{
				vx[i] = 1;
				break;
			}
		}
		if(live==n)
			perfect = 1;
		else
		{
			min = INF;
			for(i = 0; i < n; i++)
				for(j = 0; vx[i]&&j < n; j++)
					if(!vy[j])
						if((t = -(lx[i]+ly[j]-edge[i][j]))<min)
							min = t;
			for(i = 0; i < n; i++)
			{
				if(vx[i])
					lx[i] += min;
				if(vy[i])
					ly[i] -= min;
			}
		}
	}
}

int main()
{
	int i, k, cost;

	while(init())
	{
		cost = 0;
		if(!error)
		{
			puts("-1");
			continue;
		}
		for(k = 1; k <= K; k++)
		{
			get_graph(k);
			KM();
			for (i = 0; i < n; i++)
				cost += edge[link[i]][i];
			cost -= pp;
		}
		printf("%d\n",cost);
	}
	return 0;
}