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;}

1楼Java_beginer12小时前

在武汉集训感觉怎么样，现在201已经有两个回家了；无语，今年大一的不知道怎么了；似乎在这上面已经没有兴趣了