HDU 3315 My Brute(二分图最优匹配:优先用原匹配边)
http://acm.hdu.edu.cn/showproblem.php?pid=3315
题意:
有S1到Sn这n个勇士要和X1到Xn这n个勇士决斗,初始时,Si的决斗对象是Xi. 如果Si赢了Xi,那么你将获得Vi分,否则你将获得-Vi分. Si和Xi对决时,Si有初始生命Hi,初始攻击Ai, Xi有初始生命Pi,初始攻击Bi. 且Si先出手,然后Xi失去Ai生命,之后如果Xi没死,那么Xi出手,Si失去Bi生命.直到有一方的生命值<=0时,决斗结束.
现在要你重新安排S和X的决斗顺序,使得你能获得的分最多.如果有多个最优解,你要选取那个维持初始决斗顺序最多的解.
分析:
其实本题除了该二分图的权值需要自己去求之外,其他的部分基本上和HDU2853是一样的:
http://blog.csdn.net/u013480600/article/details/38736501
具体二分图处理部分这里就不做赘述了.
关于求初始左i点到右j点的权值,只需要用一个循环判断哪边的HP值先为0即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
struct Max_Match
{
int n;
int W[maxn][maxn],Lx[maxn],Ly[maxn];
bool S[maxn],T[maxn];
int left[maxn];
bool match(int i)
{
S[i]=true;
for(int j=1;j<=n;j++)if(Lx[i]+Ly[j]==W[i][j] && !T[j])
{
T[j]=true;
if(left[j]==-1 || match(left[j]))
{
left[j]=i;
return true;
}
}
return false;
}
void update()
{
int a=1<<30;
for(int i=1;i<=n;i++)if(S[i])
for(int j=1;j<=n;j++)if(!T[j])
a=min(a, Lx[i]+Ly[j]-W[i][j]);
for(int i=1;i<=n;i++)
{
if(S[i]) Lx[i] -=a;
if(T[i]) Ly[i] +=a;
}
}
int solve(int n)
{
this->n=n;
memset(left,-1,sizeof(left));
for(int i=1;i<=n;i++)
{
Lx[i]=Ly[i]=0;
for(int j=1;j<=n;j++)
Lx[i]=max(Lx[i], W[i][j]);
}
for(int i=1;i<=n;i++)
{
while(true)
{
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
if(match(i)) break;
else update();
}
}
int ans=0;
for(int i=1;i<=n;i++) ans+=W[left[i]][i];
return ans;
}
}KM;
int n;
int v[maxn],h[maxn],p[maxn],a[maxn],b[maxn];//遵循题意
int W[maxn][maxn];
int ack(int i,int j)//返回左i与右j的输赢比分
{
int hpi=h[i],hpj=p[j];//两者血量
int vi=a[i],vj=b[j];//两者攻击
while(hpi && hpj)
{
hpj-=vi;
if(hpj<=0) return v[i];
hpi-=vj;
if(hpi<=0) return -v[i];
}
}
int main()
{
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
W[i][j]=ack(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
KM.W[i][j]=W[i][j]*(n+1);
if(i==j) ++KM.W[i][j];
}
int ans=KM.solve(n);
int v1=ans/(n+1);//最优匹配权值和
int v2=ans%(n+1);//最优匹配用到的老边数
if(v1<=0) printf("Oh, I lose my dear seaco!\n");
else printf("%d %.3lf%%\n",v1,100.0*v2/n);
}
return 0;
}
分享到:
相关推荐
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
HDUACM2010版13二分匹配及其应用.ppt
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
杭电ACMhdu1163
HDU1059的代码
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
hdu acm 教案 二分匹配及其应用 hdu acm 教案 二分匹配及其应用
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
搜索 dfs 解题代码 hdu1241
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)