题意
给出4*N个同学，每个宿舍4个人。输入先是N行，每行4个数，代表原来是哪四个人在一个宿舍。再N行，代表现在是哪四个人在一个宿舍，求最少多少人需要换宿舍。
思路
处理出i宿舍向现在宿舍j转变需要换动x个人，然后就变成了带权二分图匹配。
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 200+66 #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define mod 1000000007 #define INF 0x3f3f3f3f struct KM { int nx,ny; int linker[maxn]; int slack[maxn]; int lx[maxn],ly[maxn]; int visx[maxn],visy[maxn]; int w[maxn][maxn]; void init(int x,int y) { nx=x; ny=y; memset(w,INF,sizeof(w)); } int dfs(int x) { visx[x]=1; for(int y=1; y<=ny; y++) { if(visy[y]) continue; int tmp=lx[x]+ly[y]-w[x][y]; if(tmp==0) { visy[y]=1; if(linker[y]==-1||dfs(linker[y])) { linker[y]=x; return 1; } } else if(slack[y]>tmp) slack[y]=tmp; } return 0; } int km() { int i,j; memset(linker,-1,sizeof(linker)); memset(ly,0,sizeof(ly)); for(i=1; i<=nx; i++) for(j=1,lx[i]=-INF; j<=ny; j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(int x=1; x<=nx; x++) { for(i=1; i<=ny; i++) slack[i]=INF; while(1) { memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(dfs(x)) break; int d=INF; for(i=1; i<=ny; i++) if(!visy[i]&&d>slack[i]) d=slack[i]; for(i=1; i<=nx; i++) if(visx[i]) lx[i]-=d; for(i=1; i<=ny; i++) if(visy[i]) ly[i]+=d; else slack[i]-=d; } } int res=0; for(i=1; i<=ny; i++) if(linker[i]!=-1) res+=w[linker[i]][i]; return res; } }kk; int n,x[maxn][4],y[maxn][4]; int deal(int xx,int yy) { int num=0; rep(i,0,3) { rep(j,0,3) { if(x[xx][i]==y[yy][j])num++; } } return 4-num; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=0;j<4;j++) scanf("%d",&x[i][j]); for(int i=1;i<=n;i++) for(int j=0;j<4;j++) scanf("%d",&y[i][j]); kk.init(n,n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) kk.w[i][j]=-deal(i,j); printf("%d\n",-kk.km()); return 0; }
