hdu 2853 Assignment (二分图最佳匹配，KM算法+数论，做法太神)
题意：n个公司，m个任务（m>=n),一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。 然后给出n个数，表示初始钦定（雾）这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少，以及需要改变的安排数量。
思路：最大val很好求，KM就好。。。但是，怎么才能保证改变的安排数最少呢？ 尤其是当两个安排val一样的时候，如何才能保证优先选已经安排好的，而不取选另一个呢？
并没有想出来，看了题解T T
太神辣。
由于KM算法会根据权值来选取，权值大的会优先。
如果我们把每个权值*k(k>n)，然后对于已经钦定的安排，每个权值再+1.
这样，钦定的安排就会有更高的优先级，最后统计的时候除以k,那么权值答案不会有影响（利用到了初等数论的整除知识。。。？）
然后这样做该有一个好处。
不除以k的权值和再模k,就是没有改变的安排数。
原因是由于没有钦定的安排的权值每个都乘了k,最后%k都为0，只有那些钦定的安排每个会贡献1.
又由于k>n,这样就保证了正确性。
这做法太神了。。。。。吓傻了。。。。
我试着推广一下。。。？
对于根据权值来决定优先顺序，但是权值相同的时候还是需要对一些赋有更高的优先权的模型。。。？
除了再增加一维的大家都能想到的做法。。。这样的做法是不是有通用性呢。。。？
做法太神，我得慢慢体会。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年06月03日 星期五 14时35分46秒
4File Name :code/hdu/2853.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 = 55;
34int n,m;
35int w[N][N];
36int id[N];
37int lx[N],ly[N];
38int link[N];
39bool visx[N],visy[N];
40int slk[N];
41int num;
42
43bool find( int u)
44{
45 visx[u] = true;
46
47 for ( int v = 1 ; v <= m ;v++)
48 {
49 if(visy[v]) continue;
50 int tmp = lx[u] + ly[v] - w[u][v];
51
52 if (tmp==0)
53 {
54 visy[v] = true;
55
56 if (link[v]==-1||find(link[v]))
57 {
58 link[v] = u;
59 return true;
60 }
61 }else if (tmp<slk[v]) slk[v] = tmp;
62
63 }
64 return false;
65}
66
67int KM()
68{
69 ms(link,-1);
70 ms(lx,0);
71 ms(ly,0);
72
73 for ( int i = 1 ; i <= n ; i++)
74 for ( int j = 1 ; j <= m ; j++)
75 lx[i] = max(lx[i],w[i][j]);
76
77 for ( int i = 1 ; i <= n ; i++)
78 {
79 ms(slk,0x3f);
80
81 while (1)
82 {
83 ms(visx,false);
84 ms(visy,false);
85
86 if (find(i)) break;
87
88 int d = inf;
89
90 for ( int j = 1 ; j <= m ; j++)
91 if (!visy[j]&&slk[j]<d) d = slk[j];
92
93 for ( int j = 1 ; j <= n ; j++)
94 if (visx[j]) lx[j]-=d;
95
96 for ( int j = 1 ; j <= m ; j++)
97 if (visy[j]) ly[j]+=d; else slk[j]-=d;
98 }
99 }
100
101 int res = 0 ;
102 for ( int i = 1 ; i <= m ; i++)
103 if (link[i]>-1)
104 {
105 res = res + w[link[i]][i]/N;
106 num = num + w[link[i]][i];
107 }
108
109// cout<<"num:"<<num<<endl;
110 num%=N;
111
112 return res;
113}
114int main()
115{
116 #ifndef ONLINE_JUDGE
117 freopen("code/in.txt","r",stdin);
118 #endif
119
120 while (scanf("%d%d",&n,&m)!=EOF)
121 {
122
123 ms(w,0);
124 num = 0 ;
125 for ( int i = 1 ; i <= n ; i++)
126 for ( int j = 1 ; j <= m ; j++)
127 scanf("%d",&w[i][j]),w[i][j]*=N;
128
129 int sum = 0;
130 for ( int i = 1 ; i <= n ; i++)
131 {
132 scanf("%d ",&id[i]);
133 sum = sum + w[i][id[i]]/N;
134 w[i][id[i]]++; //太神了。
135 }
136
137 int ans = KM();
138
139 printf("%d %d\n",n-num,ans-sum);
140 }
141
142 #ifndef ONLINE_JUDGE
143 fclose(stdin);
144 #endif
145 return 0;
146}
147
148
149
150
151
152
153
154/* ***********************************************
155Author :111qqz
156Created Time :2016年06月03日 星期五 14时35分46秒
157File Name :code/hdu/2853.cpp
158************************************************ */
159
160#include <cstdio>
161#include <cstring>
162#include <iostream>
163#include <algorithm>
164#include <vector>
165#include <queue>
166#include <set>
167#include <map>
168#include <string>
169#include <cmath>
170#include <cstdlib>
171#include <ctime>
172#define fst first
173#define sec second
174#define lson l,m,rt<<1
175#define rson m+1,r,rt<<1|1
176#define ms(a,x) memset(a,x,sizeof(a))
177typedef long long LL;
178#define pi pair < int ,int >
179#define MP make_pair
180
181using namespace std;
182const double eps = 1E-8;
183const int dx4[4]={1,0,0,-1};
184const int dy4[4]={0,-1,1,0};
185const int inf = 0x3f3f3f3f;
186const int N = 55;
187int n,m;
188int w[N][N];
189int id[N];
190int lx[N],ly[N];
191int link[N];
192bool visx[N],visy[N];
193int slk[N];
194int num;
195
196bool find( int u)
197{
198 visx[u] = true;
199
200 for ( int v = 1 ; v <= m ;v++)
201 {
202 if(visy[v]) continue;
203 int tmp = lx[u] + ly[v] - w[u][v];
204
205 if (tmp==0)
206 {
207 visy[v] = true;
208
209 if (link[v]==-1||find(link[v]))
210 {
211 link[v] = u;
212 return true;
213 }
214 }else if (tmp<slk[v]) slk[v] = tmp;
215
216 }
217 return false;
218}
219
220int KM()
221{
222 ms(link,-1);
223 ms(lx,0);
224 ms(ly,0);
225
226 for ( int i = 1 ; i <= n ; i++)
227 for ( int j = 1 ; j <= m ; j++)
228 lx[i] = max(lx[i],w[i][j]);
229
230 for ( int i = 1 ; i <= n ; i++)
231 {
232 ms(slk,0x3f);
233
234 while (1)
235 {
236 ms(visx,false);
237 ms(visy,false);
238
239 if (find(i)) break;
240
241 int d = inf;
242
243 for ( int j = 1 ; j <= m ; j++)
244 if (!visy[j]&&slk[j]<d) d = slk[j];
245
246 for ( int j = 1 ; j <= n ; j++)
247 if (visx[j]) lx[j]-=d;
248
249 for ( int j = 1 ; j <= m ; j++)
250 if (visy[j]) ly[j]+=d; else slk[j]-=d;
251 }
252 }
253
254 int res = 0 ;
255 for ( int i = 1 ; i <= m ; i++)
256 if (link[i]>-1)
257 {
258 res = res + w[link[i]][i]/N;
259 num = num + w[link[i]][i];
260 }
261
262// cout<<"num:"<<num<<endl;
263 num%=N;
264
265 return res;
266}
267int main()
268{
269 #ifndef ONLINE_JUDGE
270 freopen("code/in.txt","r",stdin);
271 #endif
272
273 while (scanf("%d%d",&n,&m)!=EOF)
274 {
275
276 ms(w,0);
277 num = 0 ;
278 for ( int i = 1 ; i <= n ; i++)
279 for ( int j = 1 ; j <= m ; j++)
280 scanf("%d",&w[i][j]),w[i][j]*=N;
281
282 int sum = 0;
283 for ( int i = 1 ; i <= n ; i++)
284 {
285 scanf("%d ",&id[i]);
286 sum = sum + w[i][id[i]]/N;
287 w[i][id[i]]++; //太神了。
288 }
289
290 int ans = KM();
291
292 printf("%d %d\n",n-num,ans-sum);
293 }
294
295 #ifndef ONLINE_JUDGE
296 fclose(stdin);
297 #endif
298 return 0;
299}