二分圖最大匹配(類實現)
/************************************************************************* Author: WHU_GCC Created Time: 2008/2/12 10:33:54 File Name: 二分圖最大匹配(類實現).cpp Description: ************************************************************************/ #include using namespace std; #define out(x) (cout << #x << ": " << x << endl) typedef long long int64; const int maxint = 0x7FFFFFFF; const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL; template void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; } template void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; } const int maxnx = 100, maxny = 100; class match_c { public: void init(int _nx, int _ny); void add_edge(int u, int v); int make_match(); private: int nx, ny; int mlink[maxny]; int mat[maxnx][maxny], done[maxny]; int find(int k); }; void match_c::init(int _nx, int _ny) { nx = _nx; ny = _ny; memset(mat, 0, sizeof(mat)); } inline void match_c::add_edge(int u, int v) { mat[u][v] = 1; } int match_c::find(int k) { int i, tmp; for (i = 0; i < ny; i++) if (!done[i] && mat[k][i] && mlink[i] == -1) { mlink[i] = k; done[i] = 1; return 1; } for (i = 0; i < ny; i++) if (!done[i] && mat[k][i]) { tmp = mlink[i]; mlink[i] = k; done[i] = 1; if (tmp == -1 || find(tmp)) return 1; mlink[i] = tmp; } return 0; } int match_c::make_match() { int i, sum; memset(mlink, -1, sizeof(mlink)); for (i = 0; i < nx; i++) { memset(done, 0, sizeof(done)); match_c::find(i); } sum = 0; for (i = 0; i < ny; i++) if (mlink[i] != -1) sum ++; return sum; } int main() { return 0; }