2014
02-17

# 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;
}

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;