HDU 3315 My Brute （KM 或 最大流）

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

HDU “Valentines Day” Open Programming Contest 2010-02-14

 

 

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