#include<iostream>
using namespace std;
int n,m,k;
const int INF=100000000;//  无穷大 

int shkp_need[60][60],supply[60][60],transport[60][60][60];//记录输入 
int totneed[60],totsupply[60];//总需求与总供给 
int now1[60],now2[60];//每种商品有多少需求与供给 
int edgeshkp[60][240],edgesupply[60][240];//记录edge中每个点来自哪个shopkeeper或者supply 

int edge[60][240][240],match[240];
bool xckd[240],yckd[240]; // Xi与Yi是否在交错树上 
bool map[60][240][240]; // 二分图的相等子图, map[i][j] = true 代表Xi与Yj有边 


int cost;
int init() //初始化与输入 
{
    for(int i=0;i<=k;i++)
    {
    	totneed[i]=0;
    	totsupply[i]=0;
    	now1[i]=0;
    	now2[i]=0;
    }
    for(int i=0;i<=k;i++)
    {
    	for(int j=0;j<240;j++)
    	{
     		for(int l=0;l<240;l++)
     			edge[i][j][l]=-INF;
 			edgeshkp[i][j]=-1;
    		edgesupply[i][j]=-1;
      	}
    }
	for(int i=0;i<n;i++)
	{
 		for(int j=0;j<k;j++)
 		{
 			scanf("%d",&shkp_need[i][j]);
 			totneed[j]+=shkp_need[i][j];
 			for(int l=0;l<shkp_need[i][j];l++)//记录edge中每个点来自哪个shopkeeper或者supply 
       		{
             	edgeshkp[j][now1[j]]=i;
             	now1[j]++;
          	}   	
		} 			
  	}
  	for(int i=0;i<m;i++)
	{
 		for(int j=0;j<k;j++)
 		{
 			scanf("%d",&supply[i][j]);
 			totsupply[j]+=supply[i][j];
 			for(int l=0;l<supply[i][j];l++)//记录edge中每个点来自哪个shopkeeper或者supply 
       		{
             	edgesupply[j][now2[j]]=i;
             	now2[j]++;
          	}   	
		} 			
  	}
  	for(int i=0;i<k;i++)
	{
 		for(int j=0;j<n;j++)
 		{
   			for(int l=0;l<m;l++)
   				scanf("%d",&transport[i][j][l]);
     	}
  	}
  	for(int i=0;i<k;i++)
  	{
   		if(totneed[i]>totsupply[i])
   			return 0;
    }
    cost=0;
    return 1;
}

void make()//建图 
{
    memset(map,false,sizeof(map));
    memset(xckd,false,sizeof(xckd));
    memset(yckd,false,sizeof(yckd));
	for(int i=0;i<k;i++)
	{
 		for(int j=0;j<now1[i];j++)
 		{
 		    int shkp=edgeshkp[i][j];
   			for(int l=0;l<now2[i];l++)
   			{
   			    int supply=edgesupply[i][l];
   				edge[i][j][l]=-transport[i][shkp][supply];//由于求最小权值匹配，所以先取负数 
   			}				
     	}
  	}
}

int max(int a,int b)
{
	return a>b?a:b;
}

int min(int a,int b)
{
	return a<b?a:b;
}

bool hungary(int kind,int p)//匈牙利算法求最大匹配 
{
	int mx=now2[kind];
	for(int i=0;i<mx;i++)
	{
 		if(!yckd[i]&&map[kind][p][i])
 		{
   			yckd[i]=true;
   			if(match[i]==-1||hungary(kind,match[i]))
   			{
          		match[i]=p;
          		return true;
           	}
           	if(match[i]!=-1) 
            	xckd[match[i]]=true;
     	}
  	}
  	return false;
}

void KM_Match(int kind)//KM算法求最大权值匹配 
{
	int mx=now1[kind];
	int lx[240],ly[240];  
	for(int i=0;i<mx;i++) 
 	{ 
        lx[i]=-INF;  
        for(int j=0;j<now2[kind];j++) 
        {
         	lx[i]=max(lx[i],edge[kind][i][j]);
          	ly[j]=0; 
      	}   	
	}
	bool perfect=false;
	while(!perfect)
	{
   		for(int i=0;i<mx;i++) 
 		{ 
            for(int j=0;j<now2[kind];j++) 
            { 
            	if(lx[i]+ly[j]==edge[kind][i][j]) 
             		map[kind][i][j]=true; 
            	else 
             		map[kind][i][j]=false; 
    	 	} 
     	}
		int live=0;
		for(int i=0;i<=now2[kind];i++)
			match[i]=-1;
		for(int i=0;i<mx;i++)
		{
     		memset(xckd, false, sizeof(xckd)); 
         	memset(yckd, false, sizeof(yckd));
         	if(hungary(kind,i))
         		live++;
     		else 
       		{ 
            	xckd[i]=true; 
            	break; 
         	}
       	}
       	if(live==mx)
       		perfect=true;
   		else
   		{
     		int ex=INF;
     		for(int i=0;i<mx;i++)
     		{
           		for(int j=0;xckd[i]&&j<now2[kind];j++)
           		{
             		if(!yckd[j])
               			ex=min(ex, lx[i]+ly[j]-edge[kind][i][j]);
              	}
            }
            for(int i=0;i<mx;i++) 
            { 
            	if(xckd[i])
             		lx[i]-=ex; 
         	}
         	for(int i=0;i<now2[kind];i++)
         	{
          		if(yckd[i])
            		ly[i]+=ex; 
           	}
      	}
  	}
}

int main()
{
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
	    if(n==0&&m==0&&k==0)
	    	break;
 		if(init())
 		{
 		    make();
 		    for(int i=0;i<k;i++)
 		    {
 		    	KM_Match(i);
   				for(int j=0;j<now2[i];j++) 
       			{
       			    if(match[j]!=-1)
      					cost+=edge[i][match[j]][j]; 
   				} 
 		 	}
     		printf("%d\n",-cost);   	
       	}
 		else
 			printf("-1\n");
  	}
	return 0;
}

• 有没有补点？ (0) 20053565 2008-08-23 03:00:11
  • 我用负权值做的啊 补点的话权值怎么处理呢？不过我求匹配的时候如果阶较小的部集都侵润了的就匹配结束了 这样不行么？ (56) mopishv1 2008-08-23 18:04:42
  • 过了 谢谢 大牛 呵呵 (0) mopishv1 2008-08-23 20:11:05