Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个我认为比较好的模板// This code performs maximum bipartite matching. // // Running time: O(|E| |V|) -- often much faster in practice // // INPUT: w[i][j] = edge between row node i and column node j // OUTPUT: mr[i] = assignment for row node i, -1 if unassigned // mc[j] = assignment for column node j, -1 if unassigned // function returns number of matches made #include <vector> using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; bool FindMatch(int i, const VVI &w, VI &mr, VI &mc, VI &seen) { for (int j = 0; j < w[i].size(); j++) { if (w[i][j] && !seen[j]) { seen[j] = true; if (mc[j] < 0 || FindMatch(mc[j], w, mr, mc, seen)) { mr[i] = j; mc[j] = i; return true; } } } return false; } int BipartiteMatching(const VVI &w, VI &mr, VI &mc) { mr = VI(w.size(), -1); mc = VI(w[0].size(), -1); int ct = 0; for (int i = 0; i < w.size(); i++) { VI seen(w[0].size()); if (FindMatch(i, w, mr, mc, seen)) ct++; } return ct; } #include <cstdio> int main() { int n, m, s, t; while (scanf("%d%d", &n, &m) != EOF) { VVI w = VVI(n); VI mr, mc; for (int i = 0; i < n; i++) { w[i] = VI(m, 0); scanf("%d", &s); for (int j = 0; j < s; j++) { scanf("%d", &t); w[i][t-1] = 1; } } printf("%d\n", BipartiteMatching(w, mr, mc)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator