Maximum Bipartite Matching
#include <iostream> #include <vector> #define MAX 10000 // max(|A|,|B|) using namespace std; #define INPUT_FILE "input.in" #define OUTPUT_FILE "input.out" int M[MAX] = {0}; // B--A |M| = |B| int V[MAX] = {0}; vector< vector<int> > W(MAX); // A--B int k; int dfs( int b ) { if( V[b] != k ) { V[b] = k; for( int j = 0; j < W[b].size(); j++ ) { if( M[ W[b][j] ] == 0 || dfs( M[ W[b][j] ] ) ) { M[ W[b][j] ] = b; return 1; } } } return 0; } int main() { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else freopen(INPUT_FILE, "r", stdin); freopen(OUTPUT_FILE, "w", stdout); #endif int n, m; // n = |A| // m = |B| cin >> n >> m; for (int i = 1; i <= n; i++) { int a; cin >> a; while (a != 0) { W[i].push_back(a); cin >> a; } } for(k = 1; k <= n; k++) dfs(k); int res = 0; for(int i = 1; i <= m; i++) res+= (M[i] != 0)?1:0; for(int i = 1; i <= m; i++) { if( M[i] != 0 ) { printf("%d %d\n", M[i], i); // A--B } } return 0; }
page revision: 4, last edited: 16 Mar 2007 18:29