二分图最大覆盖问题的匈牙利算法
最大流问题（Maximum flow problem）中有一类很重要的问题被称为最大二分匹配问题（Maximum-bipartite-matching problem）。很多现实中的例子可以被建模成该问题，如经典的任务分配问题（Task assignment problem）等等。这里介绍一种常用解法-匈牙利算法（Hungarian method ）。
这类问题在各种竞赛题中也出现得比较多，有些形式直接，有些则比较隐含。这类问题多半可以抽象为这样一个问题：给定一个n x m棋盘，其中指定点放一些子，然后问最少放多少个车（只能横竖走），可以将所有预放的子吃掉，或者问如果指定点是间隔，最多可以放多少个车而相互不会吃掉。比较直接能被建模成最大二分匹配问题的如pku 3041 Asteroids（http://poj.org/problem?id=3041）。
#include <iostream>using namespace std;#define N128// if we can add a edge from node a into the solution bool dfs(int a, int grid[N][N], int *res, bool *visit, int n, int m){int j;for (j = 0; j < m; ++j) { // for each column. i.e. each node on the right side of the bipartite graphif (grid[a][j] && !visit[j]) { // there is an edge between node a and j, and it hasn't been visitedvisit[j] = 1;if (res[j] == 0 || dfs(res[j], grid, res, visit, n, m)) { // node j has no maching node yet, or there is an augmenting path from res[j]res[j] = a;return true;}}}return false;}int main(){int n, m;char c;int i;int count = 0;int grid[N][N];// grid[i][j] is 1 representing there is an edge between node i and j in the bipartile graphbool visit[N];// visit[i] is 1 if node i has been visitedint res[N];// res[i] represents the maching mode of node imemset(visit, 0, sizeof(bool) * N);memset(grid, 0, sizeof(int) * N * N);memset(res, 0, sizeof(int) * N);// construct the gridcin >> n >> m;for ( i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> c;grid[i][j] = (c == 'X') ? 1 : 0;}}cout << "input over" << endl;// main bodyfor (i = 0; i < n; ++i) { // for each row, i.e. each node on the left side of the bipartite graphmemset(visit, 0, sizeof(bool) * N);// clear the visit infomationif (dfs(i, grid, res, visit, n, m)) count++;}cout << "count = " << count << endl;return 0;}