HDU 3315 My Brute

神奇的偏移量啊。其实一点也不神奇。。直接上KM就是了。
  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <vector>
  6 #define maxn 105
  7 using namespace std;
  8 
  9 struct KM
 10 {
 11     vector<int> G[maxn];
 12     int W[maxn][maxn],n;
 13     int Lx[maxn],Ly[maxn];
 14     int left[maxn];
 15     bool S[maxn],T[maxn];
 16 
 17     void init(int n)
 18     {
 19         this->n = n;
 20         for(int i = 0;i < n;i++)    G[i].clear();
 21         memset(W,0,sizeof(W));
 22     }
 23 
 24     void add_edge(int u,int v,int w)
 25     {
 26         G[u].push_back(v);
 27         W[u][v] = w;
 28     }
 29 
 30     bool match(int i)
 31     {
 32         S[i] = true;
 33         for(int k = 0;k < G[i].size();k++)
 34         {
 35             int j = G[i][k];
 36             if(Lx[i] + Ly[j] == W[i][j] && !T[j])
 37             {
 38                 T[j] = true;
 39                 if(left[j] == -1 || match(left[j]))
 40                 {
 41                     left[j] = i;
 42                     return true;
 43                 }
 44             }
 45         }
 46         return false;
 47     }
 48 
 49     void update()
 50     {
 51         int a = 1<<30;
 52         for(int i = 0;i < n;i++)    if(S[i])
 53             for(int k = 0;k < G[i].size();k++)
 54             {
 55                 int j = G[i][k];
 56                 if(!T[j])   a = min(a,Lx[i] + Ly[j] - W[i][j]);
 57             }
 58         for(int i = 0;i < n;i++)
 59         {
 60             if(S[i])    Lx[i] -= a;
 61             if(T[i])    Ly[i] += a;
 62         }
 63     }
 64 
 65     void solve()
 66     {
 67         for(int i = 0;i < n;i++)
 68         {
 69             Lx[i] = *max_element(W[i],W[i] + n);
 70             left[i] = -1;
 71             Ly[i] = 0;
 72         }
 73 
 74         for(int i = 0;i < n;i++)
 75         {
 76             while(1)
 77             {
 78                 for(int j = 0;j < n;j++)    S[j] = T[j] = 0;
 79                 if(match(i))    break;
 80                 else            update();
 81             }
 82         }
 83     }
 84 };
 85 
 86 KM solver;
 87 int V[maxn],H[maxn],P[maxn],A[maxn],B[maxn];
 88 bool check(int i,int j){
 89     int hh = H[i],aa = A[i];
 90     int pp = P[j],bb = B[j];
 91     while(1){
 92         pp -= aa;
 93         if(pp <= 0) return 1;
 94         hh -= bb;
 95         if(hh <= 0) return 0;
 96     }
 97 }
 98 
 99 int main()
100 {
101     int N;
102     while(scanf("%d",&N),N){
103         solver.init(N);
104         for(int i = 0;i < N;i++)    scanf("%d",&V[i]);
105         for(int i = 0;i < N;i++)    scanf("%d",&H[i]);
106         for(int i = 0;i < N;i++)    scanf("%d",&P[i]);
107         for(int i = 0;i < N;i++)    scanf("%d",&A[i]);
108         for(int i = 0;i < N;i++)    scanf("%d",&B[i]);
109         for(int i = 0;i < N;i++)
110         for(int j = 0;j < N;j++){
111             if(check(i,j))  solver.add_edge(i,j,V[i]*100);
112             else            solver.add_edge(i,j,-V[i]*100);
113             if(i == j)      solver.W[i][j] += 1;
114         }
115         /*for(int i = 0;i < N;i++){
116             for(int j = 0;j < N;j++)
117                 printf("%d ",solver.W[i][j]);
118             printf("
");
119         }*/
120         solver.solve();
121         int ans = 0;
122         for(int i = 0;i < N;i++)
123             ans += solver.W[solver.left[i]][i];
124         //printf("%d
",ans);
125         if(ans < 0) printf("Oh, I lose my dear seaco!
");
126         else{
127             int ans1 = ans / 100;
128             double ans2 = 100.0 * (ans % 100) / N;
129             printf("%d %.3f%%
",ans1,ans2);
130         }
131     }
132     return 0;
133 }
View Code