-
Notifications
You must be signed in to change notification settings - Fork 23
/
1325.cpp
103 lines (95 loc) · 1.93 KB
/
1325.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > lnklst;
vector<int> l, r;
vector<bool> visited;
/* make all vectors one element bigger in case the index starts from 1 instead of 0 */
void init(int n1, int n2) {
lnklst.clear(); lnklst.resize(n1+1);
l.clear(); l.resize(n1+1,-1);
r.clear(); r.resize(n2+1,-1);
return;
}
void add_edge(int u, int v) {
lnklst[u].push_back(v);
return;
}
bool dfs(int u) {
for (int i=0; i<lnklst[u].size(); i++) {
int v = lnklst[u][i];
if (visited[v]) continue;
visited[v] = true;
if (r[v] < 0 || dfs(r[v])) {
l[u] = v;
r[v] = u;
return true;
}
}
return false;
}
int greedy_match(int n1) {
int match = 0;
for (int u=0; u<n1; u++) {
if (l[u] < 0) {
for (int i=0; i<lnklst[u].size(); i++) {
int v = lnklst[u][i];
if (r[v] < 0) {
l[u] = v;
r[v] = u;
match++;
break;
}
}
}
}
return match;
}
int hungarian(void) {
int n1 = l.size();
int n2 = r.size();
int match = greedy_match(n1);
for (int u=0; u<n1; u++) {
if (l[u] < 0) {
visited.clear();
visited.resize(n2);
if (dfs(u)) {
match++;
}
}
}
return match;
}
int main() {
int n, m, k, i, j, x, y;
while (true)
{
scanf("%d", &n);
if (n == 0) break;
scanf("%d %d", &m, &k);
init(n, m);
for (j = 0; j < k; j++)
{
scanf("%d %d %d", &i, &x, &y);
if (x != 0 && y != 0) add_edge(x+1, y+1);
}
printf("%d\n", hungarian());
}
//freopen("stall.dat", "r", stdin);
/*int n, m;
while (cin >> n >> m) {
init(n, m);
for (int u=1; u<=n; u++) {
int cnt;
cin >> cnt;
while (cnt--) {
int v;
cin >> v;
add_edge(u, v);
}
}
cout << hungarian() << endl;
}*/
return 0;
}