參考題解
二分圖的最優比對。圖很容易建立。再處理相似度的時候。把每個權值擴大100倍。然後再對i==j時 特殊标記。使他們的權值再++1。後面選擇的時候就很容易挑出。按原比對
比對的個數。 100*(double)(res%100)/n。即可得到第二問。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <queue>
7 using namespace std;
8
9 const int maxn = 100;
10 const int INF = 0x3f3f3f3f;
11
12 int n;
13
14 int V[maxn], H[maxn], P[maxn], A[maxn], B[maxn];
15
16 // KM algorithm
17 int W[maxn][maxn], lft[maxn];
18 int slack[maxn];
19 int Lx[maxn], Ly[maxn];
20 bool S[maxn], T[maxn];
21
22 int inline divide(int a, int b) { int ans = a / b; if(a % b) ans++; return ans; }
23
24 bool match(int u)
25 {
26 S[u] = true;
27 for(int v = 1; v <= n; v++) if(!T[v])
28 {
29 int t = Lx[u] + Ly[v] - W[u][v];
30 if(t == 0)
31 {
32 T[v] = true;
33 if(!lft[v] || match(lft[v]))
34 {
35 lft[v] = u;
36 return true;
37 }
38 }
39 else slack[v] = min(slack[v], t);
40 }
41
42 return false;
43 }
44
45 void update()
46 {
47 int a = INF;
48 for(int i = 1; i <= n; i++) if(!T[i]) a = min(a, slack[i]);
49 for(int i = 1; i <= n; i++)
50 {
51 if(S[i]) Lx[i] -= a;
52
53 if(T[i]) Ly[i] += a;
54 else slack[i] -= a;
55 }
56 }
57
58 void KM()
59 {
60 memset(Ly, 0, sizeof(Ly));
61 memset(lft, 0, sizeof(lft));
62 for(int i = 1; i <= n; i++) Lx[i] = -INF;
63 for(int i = 1; i <= n; i++)
64 for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]);
65
66 for(int i = 1; i <= n; i++)
67 {
68 memset(slack, 0x3f, sizeof(slack));
69 for(;;)
70 {
71 memset(S, false, sizeof(S));
72 memset(T, false, sizeof(T));
73 if(match(i)) break;
74 update();
75 }
76 }
77 }
78
79 int main()
80 {
81 while(scanf("%d", &n) == 1 && n)
82 {
83 for(int i = 1; i <= n; i++) scanf("%d", V + i);
84 for(int i = 1; i <= n; i++) scanf("%d", H + i);
85 for(int i = 1; i <= n; i++) scanf("%d", P + i);
86 for(int i = 1; i <= n; i++) scanf("%d", A + i);
87 for(int i = 1; i <= n; i++) scanf("%d", B + i);
88
89 //build graph
90 for(int i = 1; i <= n; i++)
91 for(int j = 1; j <= n; j++)
92 {
93 int score = V[i] * 100;
94 int round1 = divide(P[j], A[i]);
95 int round2 = divide(H[i], B[j]);
96 if(round1 > round2) score = -score;
97 if(i == j) score++;
98 W[i][j] = score;
99 }
100
101 KM();
102
103 int ans = 0;
104 for(int i = 1; i <= n; i++) ans += W[lft[i]][i];
105
106 if(ans < 0)
107 {
108 puts("Oh, I lose my dear seaco!");
109 continue;
110 }
111
112 printf("%d ", ans / 100);
113 printf("%.3f%%\n", 100.0 * (ans % 100) / n);
114 }
115
116 return 0;
117 }
代碼君
轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4802056.html