學步園

最大流問題（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 N	128

// 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 graph
		if (grid[a][j] && !visit[j]) { // there is an edge between node a and j, and it hasn't been visited
			visit[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 graph
	bool visit[N];	// visit[i] is 1 if node i has been visited
	int res[N];		// res[i] represents the maching mode of node i
	memset(visit, 0, sizeof(bool) * N);
	memset(grid, 0, sizeof(int) * N * N);
	memset(res, 0, sizeof(int) * N);

	// construct the grid
	cin >> 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 body
	for (i = 0; i < n; ++i) { // for each row, i.e. each node on the left side of the bipartite graph
		memset(visit, 0, sizeof(bool) * N);	// clear the visit infomation
		if (dfs(i, grid, res, visit, n, m)) 
			count++;
	}

	cout << "count = " << count << endl;
	return 0;
}

上面的例子中，矩陣或棋盤的行列模型可以直接轉為二分圖模型（行，列分別對應二分圖兩連）。而上面的另一類問題中（即最多可以放多少個車），就得需要在構造二分圖時作一些處理，而算法的主體是一樣的。這種問題的例子如RookAttack 2003 TCO Semifinal Round 4 - Division I, Level Three（http://community.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709）和ZOJ 1002 Fire Net（http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002）。因為這裡二分圖中的結點對應的其實不是放置障礙物的點，而是沒有放置障礙物的地方，所以如果一行有n個障礙物，就在二分圖的左邊加n+1個結點，每個結點表示在兩個障礙之間的那一段。相似地，一列有m個障礙物，就在二分圖的右邊加m+1個結點。便於理解，可以將這些分裂後的行，列後看矩陣變形後的行，列號。