| ||||||||||
| 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