hdu 3315 My Brute （二分图最佳匹配,KM算法）
题意：两个人分别各有n个怪物。进行n场pk.每只怪物必须恰好进行一场pk.如果先手的第i只怪物赢，会获得v[i]的val,输会减少v[i]的val.给出两个人n只怪物的血量和攻击力。先手的初始战斗顺序为1,2,3..n（后手的战斗顺序一直都是1,2,3..n) 现在问能否通过调整顺序使得先手获得的val最大，如果这个val大于0，表示先手可以赢。如果可以赢，那么还要求调整后的顺序和原始顺序的相似度，并且使得相似度尽可能大（If there are multiple orders, you should choose the one whose order changes the least from the original one）
思路：先根据血量和攻击力，n*n的时间处理出每场战斗的输赢信息，然后结合v[i]，得到每两个怪物战斗的先手得到的val的值。
然后和hdu 1853类似，依然希望尽可能多的安排不改变。
我们的做法仍然是把w*N,然后钦定的w再+1
然后改变个数，由于存在负数。。。和hdu 1853的处理有区别。。。
想了一下。。。其实用link数组对照初始钦定顺序就好了啊。。。
1A.爽上天。。。
最近各种1A…？好开心。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年06月03日 星期五 15时46分12秒
4File Name :code/hdu/3315.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35int val[N];
36int h[N],p[N],a[N],b[N];
37int win[N][N];
38int w[N][N];
39int lx[N],ly[N];
40bool visx[N],visy[N];
41int link[N];
42int slk[N];
43int num;
44
45
46bool find( int u)
47{
48 visx[u] = true;
49 for ( int v = 1 ; v <= n ; v++)
50 {
51 if (visy[v]) continue;
52 int tmp = lx[u] + ly[v] - w[u][v];
53 if (tmp==0)
54 {
55 visy[v] = true;
56
57 if (link[v]==-1||find(link[v]))
58 {
59 link[v] = u;
60 return true;
61 }
62 }else if (tmp<slk[v]) slk[v] = tmp;
63 }
64
65 return false;
66}
67
68int KM()
69{
70 ms(link,-1);
71 ms(lx,0xc0);
72 ms(ly,0);
73
74 for ( int i = 1 ; i <= n ; i++)
75 for ( int j = 1 ; j <= n ; j++)
76 lx[i] = max(lx[i],w[i][j]);
77
78 for ( int i = 1 ; i <= n ; i++)
79 {
80 ms(slk,0x3f);
81
82 while(1)
83 {
84 ms(visx,false);
85 ms(visy,false);
86
87 if (find(i)) break;
88
89 int d = inf;
90
91 for ( int j = 1 ; j <= n ; j++)
92 if (!visy[j]&&slk[j]<d) d = slk[j];
93
94 for ( int j = 1 ; j <= n ; j++)
95 if (visx[j]) lx[j]-=d;
96 for ( int j = 1 ; j <= n ; j++)
97 if (visy[j]) ly[j]+=d; else slk[j]-=d;
98 }
99 }
100
101 for ( int i = 1 ; i <= n ; i++)
102 {
103 if (link[i]>-1)
104 {
105 num = num + (link[i]==i);
106 }
107 }
108 // cout<<"num:"<<num<<endl;
109 //num%=N;
110 // cout<<"num:"<<num<<endl;
111 int res = 0 ;
112 for ( int i = 1 ; i <= n ; i++)
113 {
114 if (link[i]>-1)
115 {
116 if (w[link[i]][i]>0) res = res + w[link[i]][i]/N;
117 else res = res + (w[link[i]][i]-2)/N; //???
118 }
119 }
120
121 return res;
122
123
124}
125int main()
126{
127 #ifndef ONLINE_JUDGE
128 freopen("code/in.txt","r",stdin);
129 #endif
130
131 while (scanf("%d",&n)!=EOF)
132 {
133 if (n==0) break;
134 ms(w,0xc0);
135 ms(win,0);
136 num = 0;
137 for ( int i = 1 ; i <= n ; i++) scanf("%d",&val[i]);
138 for ( int i = 1 ; i <= n ; i++) scanf("%d",&h[i]);
139 for ( int i = 1 ; i <= n ; i++) scanf("%d",&p[i]);
140 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
141 for ( int i = 1 ; i <= n ; i++) scanf("%d",&b[i]);
142
143 for ( int i = 1 ;i <= n ;i++)
144 for (int j = 1 ; j <= n ; j++)
145 {
146 win[i][j] = (h[i]+b[j]-1)/b[j]+1>(p[j]+a[i]-1)/a[i]?1:-1;
147 }
148
149
150 for ( int i = 1 ;i <= n ; i++)
151 for ( int j = 1 ;j <= n ; j++)
152 w[i][j] = win[i][j]*val[i]*N;
153
154 for ( int i = 1; i <= n ; i++) w[i][i]++;
155
156 int ans = KM();
157 if (ans<=0)
158 {
159 puts("Oh, I lose my dear seaco!");
160 }
161 else
162 {
163 double ret = num*1.0/(n*1.0);
164 ret = ret * 100.0;
165 printf("%d %.3f%%\n",ans,ret);
166 }
167
168
169 }
170
171 #ifndef ONLINE_JUDGE
172 fclose(stdin);
173 #endif
174 return 0;
175}