#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 1<<28;
using namespace std;
#define MAX 1<<28;
int lx[50], ly[50];
int map[50][50];
int visitx[50], visity[50];
int match[50], slack[50];
int n, m;
int hungary(int u){
visitx[u] = 1;
int temp = 0;
for(int i = 1; i <= m; i++){
if(visity[i])
continue;
temp = lx[u] + ly[i] - map[u][i];
if(temp == 0){
visity[i] = 1;
if(match[i] == 0 || hungary(match[i])){
match[i] = u;
return 1;
}
}
else
slack[i] = min(slack[i], temp);
}
return 0;
}
int km(){
int temp = 0;
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(lx[i] < map[i][j])
lx[i] = map[i][j];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
slack[j] = MAX;
while(1){
memset(visitx, 0, sizeof(visitx));
memset(visity, 0, sizeof(visity));
if(hungary(i))
break;
else{
temp = MAX;
for(int j = 1; j <= m; j++)
if(!visity[j])
if(temp > slack[j])
temp = slack[j];
if(temp == MAX)
return 0; // 无法匹配
for(int j = 1; j <= n; j++)
if(visitx[j])
lx[j] -= temp;
for(int j = 1; j <= m; j++)
if(visity[j])
ly[j] += temp;
else
slack[j] -= temp;
}
}
}
return 1;
}
int main(){
int rewu;
while(cin >> n){
cin >> m;
int res = 0, ans = 0;
memset(map, 0, sizeof(map));
memset(match, 0, sizeof(match));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> map[i][j];
map[i][j] *= (n+1);
}
}
for(int i = 1; i <= n; i++){
cin >> rewu;
res += map[i][rewu];
map[i][rewu]++;
}
km();
for(int i = 1; i <= m; i++)
if(match[i] != 0){
cout << "match[i]: " << match[i] << endl;
cout << i << "i: " << map[match[i]][i] << " ";
ans += map[match[i]][i];
}
cout << n - res % (n+1) << " " << ans/(n+1) - res/(n+1) << endl;
cout << res << " " << ans << endl;
}
return 0;
}
找BUG：
