题目大意：
给定n，有n间宿舍 每间4人
接下来n行 是第一年学校规定的宿舍安排
接下来n行 是第二年学生的宿舍安排意愿
求满足学生意愿的最少交换次数
input
2
1 2 3 4
5 6 7 8
4 6 7 8
1 2 3 5
output
2
#include <bits/stdc++.h>
#define MAXN 205
#define INF 0x3f3f3f3f
using namespace std;
int n,mint;
int G1[MAXN][],G2[MAXN][];
int G[MAXN][MAXN],link[MAXN];
int x[MAXN],y[MAXN];
int visx[MAXN],visy[MAXN];
bool DFS(int s) {
visx[s]=;
for(int i=;i<=n;i++) {
if(visy[i]) continue;
int tmp=x[s]+y[i]-G[s][i];
if(tmp==) {
visy[i]=;
if(link[i]==- || DFS(link[i])) {
link[i]=s; return true;
}
}
else if(tmp > ) {
mint=min(mint,tmp);
}
}
return false;
}
void KM()
{
for(int i=;i<=n;i++) {
link[i]=-; y[i]=x[i]=;
for(int j=;j<=n;j++)
x[i]=max(x[i],G[i][j]);
}
for(int i=;i<=n;i++) {
while() {
mint =INF;
memset(visx,,sizeof(visx));
memset(visy,,sizeof(visy));
if(DFS(i)) break;
for(int i=;i<=n;i++) {
if(visx[i]) x[i]-=mint;
if(visy[i]) y[i]+=mint;
}
}
}
int out=;
for(int i=;i<=n;i++) out+=G[link[i]][i];
printf("%d\n",*n-out);
}
int main()
{
while(~scanf("%d",&n)) {
for(int i=;i<=n;i++)
for(int j=;j<=;j++) scanf("%d",&G1[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=;j++) scanf("%d",&G2[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) {
int cnt=;
for(int p=;p<=;p++)
for(int q=;q<=;q++)
if(G1[i][p]==G2[j][q]) cnt++;
G[i][j]=cnt;
}
KM();
} return ;
}
KM算法讲解
https://blog.csdn.net/sixdaycoder/article/details/47720471
https://blog.csdn.net/c20180630/article/details/71080521
int n,mint;
int G[MAXN][MAXN],link[MAXN];
int x[MAXN],y[MAXN];
int visx[MAXN],visy[MAXN];
bool DFS(int s) {
visx[s]=;
for(int i=;i<=n;i++) {
if(visy[i]) continue;
int tmp=x[s]+y[i]-G[s][i];
if(tmp==) {
visy[i]=;
if(link[i]==- || DFS(link[i])) {
link[i]=s; return true;
}
}
else if(tmp > ) {
mint=min(mint,tmp);
}
}
return false;
}
void KM()
{
for(int i=;i<=n;i++) link[i]=-;
for(int i=;i<=n;i++) {
while() {
memset(visx,,sizeof(visx));
memset(visy,,sizeof(visy));
if(DFS(i)) break;
for(int i=;i<=n;i++) {
if(visx[i]) x[i]-=mint;
if(visy[i]) y[i]+=mint;
}
}
}
}
模板