Assignment
题目链接：Click Here~
题目分析:
给出n个人m个任务(n<=m)，要你给每个人分配任务，每个人对每个任务都有一个效益。要求你求出n个人的最大效益。且一开始每个人手上都有一个任务，你在以后分配任务的时候，必须更换尽量少的任务使得每个人的任务效益最大。
算法分析：
一道显然的二分匹配算法。用KM求出最大的效益就好了。
建模分析：
因为，在更换最少的任务前提下的最大效益。所以，我们可以把每个任务扩大K倍(K>n)。为了使得尽量保持原先分配的任务，所以要给原先分配的任务+1。为什么这样可以呢？因为，前面我们扩大了K倍了，且K>n。所以，实质+1这个只对原先相等的权值有作用的，这就是为什么要K>n的原因。最后，在把结果除以K，就是结果。总结点减去结果求余K就是改变的数。为什么呢？因为有数学知识知道原先的每个权值都乘以了一个K。所以，不是原先分配的任务都可以被K除尽，唯一剩下的就是原先分配剩下的那个+1的值。
ACM果然是个一群高智商的人，玩的蛋疼游戏！！！
#include#include #include #include using namespace std; const int MAXN = 50 + 5; const int INF = ~0U>>1; const int K = MAXN+MAXN; int n,m,W[MAXN][MAXN]; int slack,Lx[MAXN],Ly[MAXN],Link[MAXN]; bool S[MAXN],T[MAXN]; inline bool Match(int i) { S[i] = true; for(int j = 1;j <= m;++j)if(!T[j]){ int tmp = Lx[i]+Ly[j]-W[i][j]; if(tmp==0){ T[j] = true; if(Link[j]==-1||Match(Link[j])){ Link[j] = i; return true; } } else if(tmp < slack) slack = tmp; } return false; } inline void Update(int d) { for(int i = 1;i <= n;++i) if(S[i]) Lx[i] -= d; for(int j = 1;j <= m;++j) if(T[j]) Ly[j] += d; } bool EK() { for(int i = 1;i <= n;++i){ Lx[i] = 0; for(int j = 1;j <= m;++j) Lx[i] = max(Lx[i],W[i][j]); } memset(Link,-1,sizeof(Link)); memset(Ly,0,sizeof(Ly)); slack = INF; for(int i = 1;i <= n;++i){ while(1){ memset(S,false,sizeof(S)); memset(T,false,sizeof(T)); if(Match(i)) break; if(slack==INF) return false; Update(slack); } } return true; } void Get(int& X,int& Y) { int sum = 0; for(int i = 1;i <= m;++i){ if(Link[i]!=-1) sum += W[Link[i]][i]; } Y = sum/K - Y; X = n - sum%K; } int main() { // freopen("Input.txt","r",stdin); // freopen("Out.txt","w",stdout); while(~scanf("%d%d",&n,&m)) { memset(W,0,sizeof(W)); for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ scanf("%d",&W[i][j]); W[i][j] *= K; } } int x,X,Y = 0; for(int i = 1;i <= n;++i){ scanf("%d",&x); Y += W[i][x]/K; W[i][x]++; } EK(); Get(X,Y); printf("%d %d\n",X,Y); } return 0; }