二分图最大覆盖有关问题的匈牙利算法
二分图最大覆盖问题的匈牙利算法
上面的例子中,矩阵或棋盘的行列模型可以直接转为二分图模型(行,列分别对应二分图两连)。而上面的另一类问题中(即最多可以放多少个车),就得需要在构造二分图时作一些处理,而算法的主体是一样的。这种问题的例子如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个结点。便于理解,可以将这些分裂后的行,列后看矩阵变形后的行,列号。
最大流问题(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个结点。便于理解,可以将这些分裂后的行,列后看矩阵变形后的行,列号。