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 100bool 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 1100bool 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;elsecout << "NO" << endl;return 0; }
法2：

// 725k 32MS #include <iostream> #include <vector> #include <cstring> using namespace std;#define NODE_SIZE 50struct 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 210bool 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; }

總結

以上是生活随笔為你收集整理的二分图最大匹配 -- 匈牙利算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。