One fihgt one
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2104 Accepted Submission(s): 679
Problem Description
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.
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.
Input
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.
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.
Output
One integer , the least injuries Lv Bu’s generals would get.
Sample Input
2 3 5LvBu ZhangFei 6LvBu GuanYu 5LvBu XuChu 4ZhangLiao ZhangFei 8ZhangLiao XuChu 3
Sample Output
8
Author
shǎ崽
Source
Recommend
lcy
这个题目是说吕布要和曹操打仗了，他的将军要和人家打，列出他的将军和曹操
手下将领打仗时所损失血量，求出最小血量，这个题目还是很不错的。
一开始把所有的g值初始化为-inf，然后再进行赋值，求最大就是了，还有一定就是
为了节省时间把模板slack去掉，不再进行松弛操作，还有就是关于map的用法，map
是个好东西，假如不用map,用结构体很可能超内存，还会超时，毕竟这样就已经968ms了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define M 0x3f3f3f3f
#define N 600
int g[N][N];
int lx[N],ly[N];
int slack[N],match[N];
bool visx[N],visy[N];
int n,m,t;
bool dfs(int cur)
{
visx[cur]=true;
int i,j;
for(i=1;i<=m;i++)
{
if(visy[i])
continue;
/* int t=lx[cur]+ly[i]-g[cur][i];
if(t==0)
{
visy[i]=true;
if(match[i]==-1||dfs(match[i]))
{
match[i]=cur;
return true;
}
}*/
if(!visy[i]&&lx[cur]+ly[i]==g[cur][i])
{
visy[i]=true;
if(match[i]==-1||dfs(match[i]))
{
match[i]=cur;
return true;
}
}
/* else if(slack[i]>t)
{
slack[i]=t;
}
*/
}
return false;
}
int KM()
{
memset(match,-1,sizeof(match));
memset(ly,0,sizeof(ly));
for(int i=1;i<=n;i++)
{
lx[i]=-M;
for(int j=1;j<=m;j++)
{
if(g[i][j]>lx[i])
lx[i]=g[i][j];
}
}
for(int x=1;x<=n;x++)
{
//for(int i=1;i<=m;i++)
//slack[i]=M;
while(true)
{
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(x))break;
int d=M;
for(int j=1;j<=n;j++)
if(visx[j])
{
for(int k=1;k<=m;k++)
{
if(!visy[k]&&d>lx[j]+ly[k]-g[j][k])
{
d=lx[j]+ly[k]-g[j][k];
}
}
}
/* for(int i=1;i<=m;i++)
{
if(!visy[i]&&d>slack[i])
d=slack[i];
}
*/
for(int i=1;i<=n;i++)
if(visx[i])
{
lx[i]-=d;
}
for(int i=1;i<=m;i++)
if(visy[i])ly[i]+=d;
// else slack[i]-=d;
}
}
int reslut=0;
for(int i=1;i<=m;i++)
{
if(match[i]!=-1)
{
reslut+=g[match[i]][i];
// flag++;
}
}
return reslut;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
char s1[20],s2[20];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
g[i][j]=-M;
int a;
int num1=1,num2=1;
map<string,int>ma,mb;
for(int i=1;i<=t;i++)
{
scanf("%s%s%d",s1,s2,&a);
if(!ma[s1])
ma[s1]=num1++;
if(!mb[s2])
mb[s2]=num2++;
g[ma[s1]][mb[s2]]=-a;
}
//printf("kljlsfsd");
int ans= -KM();
printf("%d\n",ans);
}
return 0;
}