首页 > ACM题库 > HDU-杭电 > HDU 2813-One fihgt one-分治-[解题报告]HOJ
2014
02-17

HDU 2813-One fihgt one-分治-[解题报告]HOJ

One fihgt one

问题描述 :

Lv Bu and his soldiers are facing a cruel war――Cao Cao had his best generals just miles away.

There’s little time , but Lv Bu is unaware of how to arrange his warriors , what he know is that he have n brave generals while Cao Cao has m , and he has k fights to choose from , he’d like to make all his n warriors participate in the battle but get the least injuries . Lv Bu is happy because there is always a good solution . So , now is your task to tell Lv Bu the least injuries his troop would get.
No one could take part in two fights.

输入:

Multiple cases. For each case ,there are three integers in the first line , namely n,m (1<=n<=m<=200)and k (n<=k<=m*n).
The next k lines are the information about k possible fights , for each line are two strings (no more than 20 characters ) and an integer. The first string indicates Lv Bu’s general and the second , of course , Cao Cao’s , and the integer is the injury Lv Bu’s general would get if this fight were chosen.

输出:

Multiple cases. For each case ,there are three integers in the first line , namely n,m (1<=n<=m<=200)and k (n<=k<=m*n).
The next k lines are the information about k possible fights , for each line are two strings (no more than 20 characters ) and an integer. The first string indicates Lv Bu’s general and the second , of course , Cao Cao’s , and the integer is the injury Lv Bu’s general would get if this fight were chosen.

样例输入:

2 3 5
LvBu ZhangFei 6
LvBu GuanYu 5
LvBu XuChu 4
ZhangLiao ZhangFei 8
ZhangLiao XuChu 3

样例输出:

8

//Accepted	496 KB	734 ms	C++	1967 B	
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
map<string,int> m1;
map<string,int> m2;
const int maxn=210;
int w[maxn][maxn];
bool s[maxn],t[maxn];
int lx[maxn],ly[maxn];
int match[maxn];
int n,m,k;
 
bool hungary(int u){
     s[u]=true;
     for(int v=1;v<=m;v++){
         if(!t[v] && lx[u]+ly[v]==w[u][v]){
            t[v]=true;//易遗忘 
            if(match[v]==-1 || hungary(match[v])){
               match[v]=u;
               return true;
            }
         }
     }
     return false;
}
int KM(){
    int ans=0;
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++){
    	lx[i]=-1<<30;//注意 
    }
    memset(ly,0,sizeof(ly));
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
          lx[i]=max(lx[i],w[i][j]);
    for(int i=1;i<=n;i++){
        while(1){
           memset(s,false,sizeof(s));
           memset(t,false,sizeof(t));
           if(hungary(i)) break;
           else{
                int a=1<<30;
                for(int j=1;j<=n;j++) if(s[j]){
                    for(int k=1;k<=m;k++) if(!t[k] && a>lx[j]+ly[k]-w[j][k])
                        a=lx[j]+ly[k]-w[j][k];
                }
                for(int j=1;j<=n;j++){
                   if(s[j]) lx[j]-=a;   
                }
                for(int j=1;j<=m;j++){
                	if(t[j]) ly[j]+=a;
                }
           }
        }
    }
    for(int i=1;i<=m;i++) if(match[i]!=-1)//
	    ans+=w[match[i]][i];
    return -ans;//易遗忘 
}
int main(){
	char name1[21],name2[21];
	int u,v,injury;
	while(scanf("%d%d%d",&n,&m,&k)!=EOF){
		m1.clear();
		m2.clear();
		u=v=1;
		for(int i=1;i<=n;i++){//不要忘了初始化图,因为此题不一定会填满n*m的边 
			for(int j=1;j<=m;j++)
			w[i][j]=-1<<30;
		}
		while(k--){
			scanf("%s%s%d",name1,name2,&injury);
			if(m1.find(name1)==m1.end()) m1[name1]=u++;//若战将没有入图 
			if(m2.find(name2)==m2.end()) m2[name2]=v++;
			w[m1[name1]][m2[name2]]=-injury;
		}
		printf("%d\n",KM());
	}
	return 0;
}

解题参考:http://blog.csdn.net/freezhanacmore/article/details/8259354


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;