-
Notifications
You must be signed in to change notification settings - Fork 1
/
P1894.cpp
87 lines (83 loc) · 2.1 KB
/
P1894.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
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned char byte;
typedef byte vertex;
#define NOT_A_VERTEX 0xff
size_t hungarian(vector<vertex> * graph, size_t left_num, size_t right_num) {
vertex * left_matching = new vertex[left_num];
fill(left_matching, left_matching + left_num, NOT_A_VERTEX);
vertex * right_matching = new vertex[right_num];
fill(right_matching, right_matching + right_num, NOT_A_VERTEX);
vertex * pre = new vertex[left_num];
fill(pre, pre + left_num, NOT_A_VERTEX);
bool * visited = new bool[right_num];
size_t result = 0;
queue<vertex> vqueue;
for (vertex v = 0; v < left_num; v++) {
fill(visited, visited + right_num, false);
vqueue.push(v);
vertex front_v, adj_v, from, to, tmp;
while (!vqueue.empty()) {
front_v = vqueue.front();
vqueue.pop();
for (auto it = graph[front_v].begin(); it != graph[front_v].end(); it++) {
adj_v = *it;
if (!visited[adj_v]) {
visited[adj_v] = true;
if (right_matching[adj_v] != NOT_A_VERTEX) {
vqueue.push(right_matching[adj_v]);
pre[right_matching[adj_v]] = front_v;
}
else {
from = front_v;
to = adj_v;
while (from != NOT_A_VERTEX) {
tmp = left_matching[from];
left_matching[from] = to;
right_matching[to] = from;
from = pre[from];
to = tmp;
}
while (!vqueue.empty()) vqueue.pop();
goto NEXT;
}
}
} //for auto
} //while
NEXT:
if (left_matching[v] != NOT_A_VERTEX) result++;
} //for (vertex v = 0; v < left_num; v++)
free(left_matching);
free(right_matching);
free(pre);
free(visited);
queue<vertex>().swap(vqueue);
return result;
}
void readByte(byte * p_byte) {
int i;
scanf("%d", &i);
*p_byte = i;
}
int main() {
byte n, m, s, v;
readByte(&n);
readByte(&m);
vector<vertex> * graph = new vector<vertex>[n];
size_t i, j;
for (i = 0; i < n; i++) {
readByte(&s);
for (j = 0; j < s; j++) {
readByte(&v);
v--;
graph[i].push_back(v);
}
}
printf("%d", hungarian(graph, n, m));
for (i = 0; i < n; i++)
vector<vertex>().swap(graph[i]);
return 0;
}