HDU-2853 Assignment

求二分最大匹配，但还要尽量接近原匹配。。。

解决方法：对于N个顶点的二分图，每条边同时乘上一个比N稍微大的数N’，然后对于在原匹配的边就都+1。

经过这样处理，求得的答案Ans乘除N’即是原图的最大匹配，而Ans对N’取余则是现匹配中原匹配的边数。

嗯这种思想以前貌似也有接触过，“乘加除余”？

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <cctype>
#include <queue>
#define rep(i, l, r) for(int i=l; i<=r; i++)
#define clr(x, c) memset(x, c, sizeof(x))
#define N 54
#define MAX 0x3fffffff
#define ll long long
using namespace std;
int read()
{
int x=0, f=1; char ch=getchar();
while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
return x*f;
}int nx, ny, ans, now, l[N], st[N], lx[N], ly[N], v[N][N];
bool vx[N], vy[N];bool Find(int x)
{
vx[x]=1;
rep(y, 1, ny)
{
if (vy[y]) continue;
int a=lx[x]+ly[y]-v[x][y];
if (!a)
{
vy[y]=1; if (!l[y] || Find(l[y])) { l[y]=x; return 1; }
}
else st[y]=min(st[y], a);
}
return false;
}inline int km()
{
clr(l, 0); clr(ly, 0); rep(i, 1, nx) lx[i]=-MAX;
rep(i, 1, nx) rep(j, 1, ny) if (lx[i]<v[i][j]) lx[i]=v[i][j];
rep(i, 1, nx)
{
rep(j, 1, ny) st[j]=MAX;
while (1)
{
clr(vx, 0); clr(vy, 0);
if (Find(i)) break; int a=MAX;
rep(j, 1, ny) if (!vy[j] && st[j]<a) a=st[j];
if (a==MAX) return 1;
rep(j, 1, nx) if (vx[j]) lx[j]-=a;
rep(j, 1, ny) if (vy[j]) ly[j]+=a; else st[j]-=a;
}
}
int a=0; rep(i, 1, ny) if (l[i]) a+=v[l[i]][i];
return a;
}int main()
{
while (~scanf("%d%d", &nx, &ny))
{
rep(i, 1, nx) rep(j, 1, ny) v[i][j]=read()*N; now=ans=0;
rep(i, 1, nx) { int a=read(); now+=v[i][a]/N; v[i][a]++; }
int ans=km();
printf("%d %d\n", nx-ans%N, ans/N-now);
}
return 0;
}