LightOJ 1237 KM求最大匹配最小匹配
来源：http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=9954#problem/G
题意：有一些人来咖啡馆开始时间和离开咖啡馆的时间，但是对应的顺序被打乱了，也就是说不知道每个人来的时间和离开的时间。有一个函数用来计算某人来咖啡馆所需要的费用，求最大能获得多少费用，最少能获得多少费用，还要判断数据是不是合法。
思路：由于每个人对应一个开始时间和结束时间，因此我们可以以此建立二分图，边的权值就是所对应的费用。当二分图匹配为人的个数时，说明数据是合法的，然后用KM算法求最大匹配最小匹配就可以了。若二分图的匹配小于人的个数，说明给的数据是非法的，输出“impossible”即可。
KM算法求最大匹配就是模板，求最小匹配可以转化为求最大匹配。在建图时，若正常情况下边的权值是a，则求最小匹配时，把边的权值赋为-a，接下来还是用KM求最大匹配，最后求和时也加边的相反数即可。
代码：
#include <iostream>#include <cstdio>#include <string.h>#include <climits>#include <algorithm>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 55;int sx[N],sy[N],vx[N],vy[N],matchx[N],tt1[N],tt2[N];int slack[N],money1[N][N],n,money2[N][N];int min(int a,int b){return a<b?a:b;}void init(){memset(sx,0,sizeof(sx));memset(sy,0,sizeof(sy));memset(matchx,-1,sizeof(matchx));memset(slack,0,sizeof(slack));}bool dfs1(int x){vx[x] = true;for(int i = 1;i <= n;++i){ int xx = sx[x] + sy[i] - money1[x][i]; if(!vy[i] && xx == 0){ vy[i] = 1;if(matchx[i] == -1 || dfs1(matchx[i])){ matchx[i] = x; return true;} } else if(slack[i] > xx) slack[i] = xx;}return false;}void bestmatch1(){for(int i = 1;i <= n;++i){while(1){ memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); for(int j = 1;j <= n;++j) slack[j] = INT_MAX; if(dfs1(i)) break; int dd = INT_MAX; for(int j = 1;j <= n;++j){ if(!vy[j] && dd > slack[j])dd = slack[j]; } for(int j = 1;j <= n;++j){ if(vx[j])sx[j] -= dd;if(vy[j])sy[j] += dd; }}}}bool dfs2(int x){vx[x] = true;for(int i = 1;i <= n;++i){ int xx = sx[x] + sy[i] - money2[x][i]; if(!vy[i] && xx == 0){ vy[i] = 1;if(matchx[i] == -1 || dfs2(matchx[i])){ matchx[i] = x; return true;} } else if(slack[i] > xx) slack[i] = xx;}return false;}void bestmatch2(){for(int i = 1;i <= n;++i){while(1){ memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); for(int j = 1;j <= n;++j) slack[j] = INT_MAX; if(dfs2(i)) break; int dd = INT_MAX; for(int j = 1;j <= n;++j){ if(!vy[j] && dd > slack[j])dd = slack[j]; } for(int j = 1;j <= n;++j){ if(vx[j])sx[j] -= dd;if(vy[j])sy[j] += dd; }}}}int main(){//freopen("1.txt","r",stdin);int numcase;scanf("%d",&numcase);for(int k = 1; k <= numcase; ++k){ int K,g; scanf("%d%d%d",&n,&K,&g); init(); memset(money1,0,sizeof(money1)); memset(money2,0,sizeof(money2)); for(int i = 1;i <= n; ++i) scanf("%d",&tt1[i]); for(int i = 1;i <= n;++i) scanf("%d",&tt2[i]); bool flag = false; for(int i = 1;i <= n;++i){ flag = false; for(int j = 1;j <= n;++j){ if(tt1[i] < tt2[j]){ flag = true; money1[i][j] = min(g,(tt2[j] - tt1[i] - K) * (tt2[j] - tt1[i] - K)); } else money1[i][j] = -10000000; } if(flag == false) break; } printf("Case %d: ",k); if(!flag) printf("impossible\n"); else{ for(int i = 1;i <= n;++i){ sx[i] = 0;sy[i] = 0;for(int j = 1;j <= n;++j){ if(money1[i][j] > sx[i]) sx[i] = money1[i][j];} } bestmatch1(); int sum1 = 0,sum2 = 0; bool isok = true; for(int i = 1;i <= n;++i){ // printf("matchx[%d]=%d\n",i,matchx[i]); if(money1[matchx[i]][i] == -10000000){ printf("impossible\n");isok = false;break; } } if(isok){ for(int i = 1;i <= n;++i){ sum1 += money1[matchx[i]][i]; } init(); for(int i = 1;i <= n;++i){ sy[i] = 0;sx[i] = INT_MIN;for(int j = 1;j <= n;++j){if(tt1[i] < tt2[j]){ money2[i][j] = 0 - (min(g,(tt2[j] - tt1[i] - K) * (tt2[j] - tt1[i] - K))); if(money2[i][j] > sx[i]) sx[i] = money2[i][j];}elsemoney2[i][j] = -10000000;} } bestmatch2(); for(int i = 1;i <= n;++i){ sum2 += (0-money2[matchx[i]][i]); } printf("%d %d\n",sum2,sum1); } }}return 0;}