minimum cost(带权二分匹配km算法).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int NMAX = 160;
int n,m,k;
int xn,yn,num;
int w[NMAX][NMAX];
int need[60][60];
int supply[60][60];
int cost[60][60][60];

bool iscould()
{
	int i,j,l,sum;
	for(i=0;i<k;i++) {
		sum = 0;
		for(j=0;j<m;j++) {
			sum += supply[j][i];
		}
		for(j=0;j<n;j++) {
			sum -= need[j][i];
		}
		if(sum < 0) {
			return false;
		}
	}
	return true;
}

void make_graph(int i)
{
	int j,l,i2,j2;
	//x is need, y is supply
	memset(w, 0,sizeof(w));
	xn = 0; yn = 0;
	for(j=0;j<n;j++) {
		for(l=0; l < need[j][i] ;l++) {
			yn = 0;
			for(i2=0;i2<m;i2++) {
				for(j2=0; j2 < supply[i2][i];j2++) {//j shop need i goods supply by i2 port
					w[xn+l][yn+j2] = - cost[i][j][i2];//minmum
				}
				yn += supply[i2][i];
			}
		}
		xn += need[j][i];
	}
	num = max(xn, yn);
}

int lx[NMAX], ly[NMAX];
bool tx[NMAX], ty[NMAX];
int match[NMAX];
bool map[NMAX][NMAX];

bool dfs(int pos)
{
	int i;
	for(i=0;i<num;i++) {
		if(map[pos][i] && !ty[i]) {
			int pre = match[i];
			match[i] = pos;
			ty[i] = true;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			match[i] = pre;
			if(pre != -1) {
				tx[pre] = true;
			}
		}
	}
	return false;
}

int KM_Match()
{
	int i,j;

	for(i=0;i<num;i++) {
		lx[i] = INT_MIN;
		ly[i] = 0;
		for(j=0;j<num;j++) {
			lx[i] = max(lx[i], w[i][j]);
		}
	}
	bool perfect = false;
	while(!perfect) {
		for(i=0;i<num;i++) {
			for(j=0;j<num;j++) {
				if(lx[i] + ly[j] == w[i][j]) {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			}
		}//make equi-graph
		int max_match = 0;
		memset(match,-1,sizeof(match));
		for(i=0; i < num ;i++) {
			memset(tx, false, sizeof(tx)); 
			memset(ty, false, sizeof(ty));
			if( dfs(i) ) {
				max_match ++;
			}
			else {
				tx[i] = true;
				break;
			}
		}
		if(max_match == num) {
			perfect = true;
		}
		else {
			int ex = INT_MAX;
			for(i=0;i<num;i++) {
				for(j=0; tx[i] && j<num;j++) {
					if(!ty[j]) {
						ex = min(ex, lx[i]+ly[j]-w[i][j]);
					}
				}
			}//find min
			for(i=0;i<num;i++) {
				if(tx[i]) {
					lx[i] -= ex;
				}
				if(ty[i]) {
					ly[i] += ex;
				}
			}
		}
	}
	int cost = 0;
	for(i=0; i < num ;i++) { 
		cost += w[ match[i] ][i];
	}
	return cost;
}

int main()
{
	int i,j,l,c;
	while(scanf("%d %d %d", &n, &m, &k)==3) {
		if(n==0 && m==0 && k==0) {
			break;
		}
		for(i=0;i<n;i++) {
			for(j=0;j<k;j++) {
				scanf("%d", &need[i][j]);
			}
		}
		for(i=0;i<m;i++) {
			for(j=0;j<k;j++) {
				scanf("%d", &supply[i][j]);
			}
		}
		for(i=0;i<k;i++) {
			for(j=0;j<n;j++) {
				for(l=0;l<m;l++) {
					scanf("%d", &cost[i][j][l]);
				}
			}
		}
		if(!iscould()) {
			puts("-1");
		}
		else {
			int ans = 0;
			for(i=0;i<k;i++) {
				make_graph(i);
				ans += KM_Match();
			}
			printf("%d\n", -ans);
		}
	}
}