`

HDU 3315 My Brute (KM 或 最大流)

    博客分类:
  • ACM
阅读更多

My Brute

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 488    Accepted Submission(s): 178


Problem Description
Seaco is a beautiful girl and likes play a game called “My Brute”. Before Valentine’s Day, starvae and xingxing ask seaco if she wants to spend the Valentine’s Day with them, but seaco only can spend it with one of them. It’s hard to choose from the two excellent boys. So there will be a competition between starvae and xingxing. The competition is like the game “My Brute”.


Now starvae have n brutes named from S1 to Sn and xingxing’s brutes are named from X1 to Xn. A competition consists of n games. At the beginning, starvae's brute Si must versus xingxing’s brute Xi. But it’s hard for starvae to win the competition, so starvae can change his brutes’ order to win more games. For the starvae’s brute Si, if it wins the game, starvae can get Vi scores, but if it loses the game, starvae will lose Vi scores. Before the competition, starvae’s score is 0. Each brute can only play one game. After n games, if starvae’s score is larger than 0, we say starvae win the competition, otherwise starvae lose it. 

It’s your time to help starvae change the brutes’ order to make starvae’s final score be the largest. If there are multiple orders, you should choose the one whose order changes the least from the original one. The original order is S1, S2, S3 … Sn-1, Sn, while the final order is up to you.

For starvae’s brute Si (maybe this brute is not the original brute Si, it is the ith brute after you ordered them) and xingxing’s brute Xi, at first Si has Hi HP and Xi has Pi HP, Si’s damage is Ai and Xi’s is Bi, in other words, if Si attacks, Xi will lose Ai HP and if Xi attacks, Si will lose Bi HP, Si attacks first, then it’s Xi’s turn, then Si… until one of them’s HP is less than 0 or equal to 0, that, it lose the game, and the other win the game.

Come on, starvae’s happiness is in your hand!
 

 

Input
First line is a number n. (1<=n<=90) Then follows a line with n numbers mean V1 to Vn. (0<Vi<1000) Then follows a line with n numbers mean H1 to Hn. (1<=Hi<=100)Then follows a line with n numbers mean P1 to Pn. (1<=Pi<=100) Then follows a line with n numbers mean A1 to An.(1<=Ai<=50) Then follows a line with n numbers mean B1 to Bn. (1<=Bi<=50) A zero signals the end of input and this test case is not to be processed.
 

 

Output
For each test case, if starvae can win the competition, print the largest score starvae can get, and then follow a real percentage means the similarity between the original order and the final order you had changed, round it to three digits after the decimal point. If starvae can’t win the competition after changing the order, please just print “Oh, I lose my dear seaco!” Maybe the sample can help you get it.
 

 

Sample Input
3 4 5 6 6 8 10 12 14 16 7 7 6 7 3 5 3 4 5 6 6 8 10 12 14 16 5 5 5 5 5 5 0
 

 

Sample Output
7 33.333% Oh, I lose my dear seaco!
 

 

Author
starvae
 

 

Source
 

 

Recommend
wxl
 

 

 

二分图的最优匹配。图很容易建立。再处理相似度的时候。把每个权值扩大100倍。然后再对i==j时 特殊标记。使他们的权值再++1。后面选择的时候就很容易挑出。按原匹配

匹配的个数。 100*(double)(res%100)/n。即可得到第二问。

 

还可以用最大流的算法,,,有机会尝试一下

 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=110;
const int INF=0x3f3f3f3f;

int n;
int linker[N],lx[N],ly[N],slack[N];
int visx[N],visy[N],w[N][N];
int v[N],h[N],p[N],a[N],b[N];

int DFS(int x){
    visx[x]=1;
    for(int y=1;y<=n;y++){
        if(visy[y])
            continue;
        int tmp=lx[x]+ly[y]-w[x][y];
        if(tmp==0){
            visy[y]=1;
            if(linker[y]==-1 || DFS(linker[y])){
                linker[y]=x;
                return 1;
            }
        }else if(slack[y]>tmp){ //不在相等子图中slack 取最小的
            slack[y]=tmp;
        }
    }
    return 0;
}

int KM(){
    int i,j;
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(i=1;i<=n;i++)      //lx初始化为与它关联边中最大的
        for(j=1,lx[i]=-INF;j<=n;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    for(int x=1;x<=n;x++){
        for(i=1;i<=n;i++)
            slack[i]=INF;
        while(1){
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(DFS(x))  //若成功(找到了增广轨),则该点增广完成,进入下一个点的增广
                break;  //若失败(没有找到增广轨),则需要改变一些点的标号,使得图中可行边的数量增加。
                        //方法为:将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数d,
                        //所有在增广轨中的Y方点的标号全部加上一个常数d
            int d=INF;
            for(i=1;i<=n;i++)
                if(!visy[i] && d>slack[i])
                    d=slack[i];
            for(i=1;i<=n;i++)
                if(visx[i])
                    lx[i]-=d;
            for(i=1;i<=n;i++)  //修改顶标后,要把所有不在交错树中的Y顶点的slack值都减去d
                if(visy[i])
                    ly[i]+=d;
                else
                    slack[i]-=d;
        }
    }
    int res=0;
    for(i=1;i<=n;i++){
        if(linker[i]==-1 || w[linker[i]][i]==-INF)
            return -1;
        res+=w[linker[i]][i];
    }
    return res;
}

int win(int x,int y){
    int hp1=h[x], hp2=p[y];
    int damage1=a[x], damage2=b[y];
    while(1){
        hp2=hp2-damage1;
        if(hp2<=0)
            return 1;
        hp1=hp1-damage2;
        if(hp1<=0)
            return 0;
    }
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d",&n) && 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++)
                if(win(i,j)){
                    w[i][j]=v[i]*100;
                    if(i==j)
                        w[i][j]++;
                }else{
                    w[i][j]=-v[i]*100;
                    if(i==j)
                        w[i][j]++;
                }
        int res=KM();
        int ans=res/100;
        if(ans>0)
            printf("%d %.3lf%%\n",ans,100*(double)(res%100)/n);
        else
            printf("Oh, I lose my dear seaco!\n");
    }
    return 0;
}

 

分享到:
评论

相关推荐

    KM匹配题集

    - **【HDU 3315】Assignment 求 KM 最大时,要求改动最少**、**【HDU 3523】My Brute 求 KM 最大时,要求改动最少**:这些题目中的“KM”可能不是指KMP算法,而是指Kuhn-Munkres算法(也称匈牙利算法),用于解决赋权...

    hdu.rar_hdu

    压缩包内的文件名“朝花夕拾——hdu”可能表示这是一系列关于HDU题目的代码记录,"朝花夕拾"是一个成语,意味着回忆过去的事情,这里可能是暗示这些代码是作者在过去解决HDU题目时留下的,现在整理出来分享或复习。...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    "hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届活动。这个压缩包可能是参赛者或教练分享的解题代码和资料。 【描述】提到的"水仙花数"问题,是计算机科学和算法竞赛中...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU acm-PPT课件

    数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程、欧几里得算法等)、组合数学(排列组合、容斥原理、鸽巢原理等)、图论(网络流、最大匹配等)。理解并运用这些数学知识,可以解决很多看似复杂的问题...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    杭电ACMhdu1163

    这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,以求在限定时间内提交正确的解决方案。这类竞赛有助于提升编程能力、算法思维以及问题解决技巧。 【标签】:“杭电”代表题目来源于杭州电子...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    Hdu1000—2169部分代码

    标签"HDu acm"进一步确认了这些代码与ACM竞赛相关的编程挑战有关,可能是参赛者或训练者为了准备比赛而编写的。在ACM竞赛中,团队需要在有限的时间内解决多个复杂的问题,因此高效的编码和算法实现至关重要。 虽然...

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU 1237代码

    Hdu 1237 解题代码

Global site tag (gtag.js) - Google Analytics