首页 > 代码库 > 二分图最大匹配 -- 匈牙利算法
二分图最大匹配 -- 匈牙利算法
Algorithm.( Augmenting Path Algorithm )
Input:
An X-Y bigraph G, a matching M in G,
and the set U of M-unsaturated vertices in X.
Idea:
Explore M-alternating paths form U,
letting S ? X and T ? Y be the sets of vertices reached.
Marks vertices of S that have been explored for path extensions.
As a vertex is reached, record the vertex from which it is reached.
Initialization:
S = U and T = ?
Iteration:
If S has no unmarked vertex,
stop and report T ∪ ( X - S ) as a minimun cover and M as a maximum matching.
Otherwise, select an unmarked x ∈ S, consider each y ∈ N( x ) such that xy ? M,
if y is unsaturated, terminate and report an M-augmenting path from U to y.
Otherwise, y is matched to some w ∈ X by M.
In this case, include y in T ( reached from x ) and include w in S ( reached from y ).
After exploring all such edges incident to x, mark x and iterate.
#include <iostream> #include <cstring> using namespace std; #define NODE_SIZE 100 bool bigraph[NODE_SIZE][NODE_SIZE]; int parent[NODE_SIZE]; bool visit[NODE_SIZE]; int num = 0; int nodes1, nodes2, edges; bool find_augmenting_path( int start_node ){ for( int end_node = 1; end_node <= nodes2; ++end_node ){ if( bigraph[start_node][end_node] && visit[end_node] == false ){ visit[end_node] = true; if( parent[end_node] == 0 || find_augmenting_path( parent[end_node] ) ){ parent[end_node] = start_node; return true; } } } return false; } int main(){ memset( bigraph, false, sizeof( bigraph ) ); memset( visit, false, sizeof( visit ) ); memset( parent, 0, sizeof( parent ) ); cin >> nodes1 >> nodes2 >> edges; for( int i = 1; i <= edges; ++i ){ int start_node, end_node; cin >> start_node >> end_node; bigraph[start_node][end_node] = true; } for( int node = 1; node <= nodes1; ++node ){ memset( visit, false, sizeof( visit ) ); if( find_augmenting_path( node ) ) num++; } cout << num << endl; return 0; }
简单应用:
在 raw * col 的棋盘上,有些格子不能放,用1 * 2 的方块铺棋盘,问能不能铺满?
比如:
思路:
对每种格子着色,黑白相间,不能放的格子除。
然后白色的格子为一个部集,黑色的格子也为一个部集,两个部集进行最大匹配,
若最后匹配数目等于黑色或者白色格子的总数,即为可行;否则,不可行。
法1:
// 1143MS #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define CHESSBOARD_SIZE 50 #define GRAPH_SIZE 1100 bool chessboard[CHESSBOARD_SIZE][CHESSBOARD_SIZE]; bool bigraph[GRAPH_SIZE][GRAPH_SIZE]; bool visit[GRAPH_SIZE]; int parent[GRAPH_SIZE]; int raws, cols, holes; bool find_augmenting_path( int source ){ for( int target = 1; target <= raws * cols; ++target ){ if( bigraph[source][target] && !visit[target] ){ visit[target] = true; if( parent[target] == 0 || find_augmenting_path( parent[target] ) ){ parent[target] = source; return true; } } } return false; } int maximum_matching(){ int ans = 0; for( int i = 1; i <= raws * cols; ++i ){ memset( visit, false, sizeof( visit ) ); if( find_augmenting_path( i ) ) ans++; } return ans; } int main(){ memset( chessboard, false, sizeof( chessboard ) ); memset( bigraph, false, sizeof( bigraph ) ); memset( visit, true, sizeof( visit ) ); memset( parent, 0, sizeof( parent ) ); cin >> raws >> cols >> holes; int num = raws * cols; for( int i = 1; i <= holes; ++i ){ int raw, col; cin >> col >> raw; chessboard[raw][col] = true; num--; } for( int raw = 1; raw <= raws; ++raw ){ for( int col = 1; col <= cols; ++col ){ if( chessboard[raw][col] ) continue; int p1 = cols * ( raw - 1 ) + col; if( raw > 1 && chessboard[raw - 1][col] == false ){ int p2 = p1 - cols; bigraph[p1][p2] = true; } if( raw < raws && chessboard[raw + 1][col]== false ){ int p2 = p1 + cols; bigraph[p1][p2] = true; } if( col > 1 && chessboard[raw][col - 1] == false ){ int p2 = p1 - 1; bigraph[p1][p2] = true; } if( col < cols && chessboard[raw][col + 1] == false ){ int p2 = p1 + 1; bigraph[p1][p2] = true; } } } int ans = maximum_matching(); if( ans == num ) cout << "YES" << endl; else cout << "NO" << endl; return 0; }
法2:
// 725k 32MS #include <iostream> #include <vector> #include <cstring> using namespace std; #define NODE_SIZE 50 struct Position{ Position(){ raw = -1; col = -1; }; Position( int r, int c ){ raw = r; col = c; }; int raw; int col; }; enum State { INIT, HOLE, BLACK, WHITE }; State chessboard[NODE_SIZE][NODE_SIZE]; Position parent[NODE_SIZE * NODE_SIZE]; bool visit[NODE_SIZE * NODE_SIZE]; int raws, cols, holes; int direction[5][3] = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 }, { 0, -1, 0 }, { 0, 0, -1 } }; bool find_augmenting_path( Position source ){ for( int i = 1; i <= 4; ++i ){ int dx = direction[i][1]; int dy = direction[i][2]; int next_raw = source.raw + dx; int next_col = source.col + dy; if( next_raw >= 1 && next_raw <= raws && next_col >= 1 && next_col <= cols ){ int one_dim_pos = cols * ( next_raw - 1 ) + next_col; if( chessboard[next_raw][next_col] == WHITE && !visit[one_dim_pos] ){ visit[one_dim_pos] = true; if( ( parent[one_dim_pos].raw == -1 && parent[one_dim_pos].col == -1 ) || find_augmenting_path( parent[one_dim_pos] ) ){ parent[one_dim_pos].raw = source.raw; parent[one_dim_pos].col = source.col; return true; } } } } return false; } int main(){ cin >> raws >> cols >> holes; vector< Position > black_rects; vector< Position > white_rects; for( int raw = 1; raw <= raws; ++raw ){ for( int col = 1; col <= cols; ++col ){ chessboard[raw][col] = INIT; } } memset( visit, false, sizeof( visit ) ); int rects = raws * cols - holes; for( int i = 1; i <= holes; ++i ){ int col, raw; cin >> col >> raw; chessboard[raw][col] = HOLE; } for( int raw = 1; raw <= raws; ++raw ){ for( int col = 1; col <= cols; ++col ){ if( chessboard[raw][col] == HOLE ) continue; if( ( col % 2 && raw % 2 ) || ( ( raw % 2 == 0 ) && ( col % 2 == 0 ) ) ){ chessboard[raw][col] = BLACK; black_rects.push_back( Position( raw, col ) ); } else{ chessboard[raw][col] = WHITE; white_rects.push_back( Position( raw, col ) ); } } } const int black_rects_num = black_rects.size(); const int white_rects_num = white_rects.size(); if( black_rects_num == 0 || rects % 2 != 0 || black_rects_num != white_rects_num ){ cout << "NO" << endl; } else{ int ans = 0; for( int i = 0; i < black_rects_num; ++i ){ memset( visit, false, sizeof( visit ) ); if( find_augmenting_path( black_rects[i] ) ) ans++; } if( ans == black_rects_num ){ cout << "YES" << endl; } else{ cout << "NO" << endl; } } return 0; }
POJ 3692
建反图,求最大独立集
#include <iostream> #include <cstring> using namespace std; #define MAX_SIZE 210 bool bigraph[MAX_SIZE][MAX_SIZE]; bool visits[MAX_SIZE]; int parents[MAX_SIZE]; int B, G, M; bool find_augmenting_path( int source ){ for( int target = 1; target <= B; ++target ){ if( bigraph[source][target] && !visits[target] ){ visits[target] = true; if( parents[target] == 0 || find_augmenting_path( parents[target] ) ){ parents[target] = source; return true; } } } return false; } int maximum_matching(){ int ans = 0; for( int source = 1; source <= G; ++source ){ memset( visits, false, sizeof( visits ) ); if( find_augmenting_path( source ) ) ans++; } return ans; } int main(){ int nCase = 1; while( true ){ memset( bigraph, true, sizeof( bigraph ) ); memset( parents, 0, sizeof( parents ) ); memset( visits, false, sizeof( visits ) ); cin >> G >> B >> M; if( G == 0 && B == 0 && M == 0 ) break; for( int i = 1; i <= M; ++i ){ int u, v; cin >> u >> v; bigraph[u][v] = false; } int max_matching = maximum_matching(); int ans = G + B - max_matching; cout << "Case " << nCase << ": " << ans << endl; nCase++; } return 0; }