首页 > ACM题库 > HDU-杭电 > HDU 3315-My Brute[解题报告]HOJ
2014
03-16

HDU 3315-My Brute[解题报告]HOJ

My Brute

问题描述 :

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”.

Trouble with Election!

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!

输入:

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.

输出:

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.

样例输入:

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

样例输出:

7 33.333%
Oh, I lose my dear seaco!

神奇的偏移量啊。其实一点也不神奇。。直接上KM就是了。

My Brute

#include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cstdlib>
 #include <vector>
 #define maxn 105
 using namespace std;
 
 struct KM
 {
     vector<int> G[maxn];
     int W[maxn][maxn],n;
     int Lx[maxn],Ly[maxn];
     int left[maxn];
     bool S[maxn],T[maxn];
 
     void init(int n)
     {
         this->n = n;
         for(int i = 0;i < n;i++)    G[i].clear();
         memset(W,0,sizeof(W));
     }
 
     void add_edge(int u,int v,int w)
     {
         G[u].push_back(v);
         W[u][v] = w;
     }
 
     bool match(int i)
     {
         S[i] = true;
         for(int k = 0;k < G[i].size();k++)
         {
             int j = G[i][k];
             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 = 0;i < n;i++)    if(S[i])
             for(int k = 0;k < G[i].size();k++)
             {
                 int j = G[i][k];
                 if(!T[j])   a = min(a,Lx[i] + Ly[j] - W[i][j]);
             }
         for(int i = 0;i < n;i++)
         {
             if(S[i])    Lx[i] -= a;
             if(T[i])    Ly[i] += a;
         }
     }
 
     void solve()
     {
         for(int i = 0;i < n;i++)
         {
             Lx[i] = *max_element(W[i],W[i] + n);
             left[i] = -1;
             Ly[i] = 0;
         }
 
         for(int i = 0;i < n;i++)
         {
             while(1)
             {
                 for(int j = 0;j < n;j++)    S[j] = T[j] = 0;
                 if(match(i))    break;
                 else            update();
             }
         }
     }
 };
 
 KM solver;
 int V[maxn],H[maxn],P[maxn],A[maxn],B[maxn];
 bool check(int i,int j){
     int hh = H[i],aa = A[i];
     int pp = P[j],bb = B[j];
     while(1){
         pp -= aa;
         if(pp <= 0) return 1;
         hh -= bb;
         if(hh <= 0) return 0;
     }
 }
 
 int main()
 {
     int N;
     while(scanf("%d",&N),N){
         solver.init(N);
         for(int i = 0;i < N;i++)    scanf("%d",&V[i]);
         for(int i = 0;i < N;i++)    scanf("%d",&H[i]);
         for(int i = 0;i < N;i++)    scanf("%d",&P[i]);
         for(int i = 0;i < N;i++)    scanf("%d",&A[i]);
         for(int i = 0;i < N;i++)    scanf("%d",&B[i]);
         for(int i = 0;i < N;i++)
         for(int j = 0;j < N;j++){
             if(check(i,j))  solver.add_edge(i,j,V[i]*100);
             else            solver.add_edge(i,j,-V[i]*100);
             if(i == j)      solver.W[i][j] += 1;
         }
         /*for(int i = 0;i < N;i++){
             for(int j = 0;j < N;j++)
                 printf("%d ",solver.W[i][j]);
             printf("\n");
         }*/
         solver.solve();
         int ans = 0;
         for(int i = 0;i < N;i++)
             ans += solver.W[solver.left[i]][i];
         //printf("%d\n",ans);
         if(ans < 0) printf("Oh, I lose my dear seaco!\n");
         else{
             int ans1 = ans / 100;
             double ans2 = 100.0 * (ans % 100) / N;
             printf("%d %.3f%%\n",ans1,ans2);
         }
     }
     return 0;
 }

View Code

 

 

参考:http://www.cnblogs.com/zhexipinnong/p/3369206.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。