1005.cpp

HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告

/* 
 * File:   Fihgt one by one.cpp
 * Author: NotOnlySuccess
 * Method: KM
 * Created on 2009??4??23??, ????9:27
 */
#include<stdlib.h>
#include<stdio.h>
#include<string>
#define MAXN 201
#define inf 0x7fffffff
#define _clr(x) memset(x,0xff,sizeof(int)*n)
struct Fight{
	char a[21],b[21];
	int hurt;
}fight[MAXN*MAXN];
char lb[MAXN][21];
char cc[MAXN][21];
int mat[MAXN][MAXN];
int kuhn_munkras(int m,int n,int* match1){
	int match2[MAXN];
	int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
	for (i=0;i<m;i++)
		for (l1[i]=-inf,j=0;j<n;j++)
			l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
	for (i=0;i<n;l2[i++]=0);
	for (_clr(match1),_clr(match2),i=0;i<m;i++){
		for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
			for (k=s[p],j=0;j<n&&match1[i]<0;j++)
				if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
					s[++q]=match2[j],t[j]=k;
					if (s[q]<0)
						for (p=j;p>=0;j=p)
							match2[j]=k=t[j],p=match1[k],match1[k]=j;
				}
		if (match1[i]<0){
			for (i--,p=inf,k=0;k<=q;k++)
				for (j=0;j<n;j++)
					if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
						p=l1[s[k]]+l2[j]-mat[s[k]][j];
			for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
			for (k=0;k<=q;l1[s[k++]]-=p);
		}
	}
	for (i=0;i<m;i++)
		ret+=mat[i][match1[i]];
	return ret;
}
int find(char a[],char b[][21],int n) {
	int i;
	for(i = 0; i < n ; i ++) {
		if(strcmp(a,b[i]) == 0) {
			break ;
		}
	}
	return i;
}
int cmp(const void *a,const void *b) {
	return strcmp((char *)a,(char *)b);
}
int main(int argc, char** argv)
{
//   	freopen("ofo.in","r",stdin);
//   	freopen("ofo.out","w",stdout);
	int n,m,i,k,j,l1,l2;
	int match[MAXN];
	while(scanf("%d%d%d",&n,&m,&k) == 3) {
		l1 = l2 = 0;
		for(i = 0; i < k ; i ++) {
			scanf("%s%s%d",fight[i].a,fight[i].b,&fight[i].hurt);
			j = find(fight[i].a,lb,l1);
			if(j == l1) {
				strcpy(lb[l1],fight[i].a);
				l1 ++;
			}
			j = find(fight[i].b,cc,l2);
			if(j == l2) {
				strcpy(cc[l2],fight[i].b);
				l2 ++;
			}
		}
		for(i = 0; i < n ; i ++) {
			for(j = 0; j < m;  j ++) {
				mat[i][j] = -99999999;
			}
		}
		qsort(lb,n,sizeof(lb[0]),cmp);
		for(i = 0;i < k ; i ++) {
			l1 = find(fight[i].a,lb,n);
			l2 = find(fight[i].b,cc,m);
			mat[l1][l2] = -fight[i].hurt;
		}
		printf("%d\n",-kuhn_munkras(n,m,match));
	}
	return (EXIT_SUCCESS);
}