大致题意:
吕布要跟曹操pk。吕布有n个小弟,曹操有m个。已知可以由k种打架的方式,每种方式都是一个吕布的小弟去虐另一个曹操的人,每种方式都有一个伤害值。而且吕布和曹操的人都只能干一架。求伤害值最少是多少。
大致思路:
二分图最小权匹配。初始值全部取负,求出最大匹配后再将这个值取负得到的就是答案。切记tire申请空间不要太给力,被MLE到shi了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax=404;
const int mMax=1005;
const int inf=1<<29;
int map[nMax][nMax];
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int n,m,e,cnt;
int find (int u){
int v,t;
sx[u]=1;
for(v=1;v<=m;v++){
if(sy[v]) continue;
t=lx[u]+ly[v]-map[u][v];
if(t==0){
sy[v]=1;
if(mapch[v]==-1||find(mapch[v])){
mapch[v]=u;
return 1;
}
}
else if(t<stack[v]) stack[v]=t;
}
return 0;
}
int KM(){
int i,j,k,d,sum=0;
cnt=0;
for(i=1;i<=m;i++)
ly[i]=0;
memset(mapch,-1,sizeof(mapch));
for(i=1;i<=n;i++){
lx[i]=-inf;
for(j=1;j<=m;j++)
if(map[i][j]>lx[i])
lx[i]=map[i][j];
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
stack[j]=inf;
while(1){
for(k=1;k<=m;k++) sy[k]=0;
for(k=1;k<=n;k++) sx[k]=0;
if(find(i)) break;
d=inf;
for(k=1;k<=m;k++)
if(!sy[k]&&stack[k]<d)
d=stack[k];
for(k=1;k<=n;k++)
if(sx[k]) lx[k]-=d;
for(k=1;k<=m;k++)
if(sy[k]) ly[k]+=d;
else stack[k]-=d;
}
}
for(i=1;i<=m;i++)
if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){
sum+=map[mapch[i]][i];
}
return sum;
}
class nodea{
public:
int id;
nodea *p[65];
nodea(){
int i;
id=-1;
for(i=0;i<65;i++)p[i]=NULL;
}
};
nodea *root;
int cnt1,cnt2;
int getnum(char *s,int &cc){
int i;
nodea *r=root;
int l=strlen(s);
for(i=0;i<l;i++){
if(r->p[s[i]-60]==NULL){
r->p[s[i]-60]=new nodea();
}
r=r->p[s[i]-60];
}
if(r->id==-1){
r->id=cc;
cc++;
}
return r->id;
}
int main(){
int i,j,k,s,a,b;
char name1[30],name2[30];
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
cnt1=cnt2=1;
root=new nodea();
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
map[i][j]=-inf;
}
}
while(k--){
scanf("%s%s%d",name1,name2,&s);
a=getnum(name1,cnt1);
b=getnum(name2,cnt2);
map[a][b]=-s;
}
printf("%d\n",-KM());
}
return 0;
}
分享到:
相关推荐
【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
“hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...