加权二分图的条件匹配问题

1. 最大权匹配

首先，对于加权二分图的条件匹配问题，最大权匹配是一个很好的解决方案。我们可以使用Kuhn-Munkres算法（又称作匈牙利算法）来求解最大权匹配。代码如下：

#include <iostream> 
#include <cstring> 
#include <cmath> 

#define INF 0x3f3f3f3f 
#define MAXN 100 

using namespace std; 

int n, m;
int g[MAXN][MAXN]; // 用二维数组存储边权 
int cx[MAXN], cy[MAXN], mk[MAXN]; 

void init() { 
  memset(g, -INF, sizeof(g)); 
  memset(cx, -1, sizeof(cx)); 
  memset(cy, -1, sizeof(cy)); 
  memset(mk, 0, sizeof(mk)); 
} 

int dfs(int x) { 
  for (int y = 1; y <= m; y++) { 
    if (mk[y]) continue; 
    int tmp = cx[x] + cy[y] - g[x][y]; 
    if (tmp == 0) { 
      mk[y] = 1; 
      if (cy[y] == -1 || dfs(cy[y])) { 
        cy[y] = x; 
        cx[x] = y; 
        return 1; 
      } 
    } 
    else mk[y] = 0; 
  } 
  return 0; 
} 

int km() { 
  for (int i = 1; i <= n; i++) { 
    while (true) { 
      int d = INF; 
      memset(mk, 0, sizeof(mk)); 
      if (dfs(i)) break; 
      for (int x = 1; x <= n; x++) 
        if (mk[x]) 
          for (int y = 1; y <= m; y++) 
            if (!mk[y]) 
              d = min(d, cx[x] + cy[y] - g[x][y]); 
      if