-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathP3386.cpp
More file actions
156 lines (143 loc) · 5.11 KB
/
P3386.cpp
File metadata and controls
156 lines (143 loc) · 5.11 KB
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned int Vertex;
#define NO_VERTEX 0xffffffff
class Hungarian {
public:
/*
返回二分图最大匹配
@param graph 图，只记录左边顶点到右边顶点的边
@param left_num 左边顶点数量，左边顶点编号 0 ~ left_num - 1
@param right_num 右边顶点数量，右边顶点编号 0 ~ right_num - 1
@return size_t 最大匹配数量
*/
virtual size_t maxMatching(vector<Vertex> * graph, size_t left_num, size_t right_num) = 0;
virtual ~Hungarian() {
}
};
//DFS实现
class DFS : public Hungarian {
public:
virtual size_t maxMatching(vector<Vertex> * graph, size_t left_num, size_t right_num);
private:
bool dfs(Vertex v);
vector<Vertex> * graph_;
Vertex * matching_;
bool * visited_;
size_t match_num_;
};
size_t DFS::maxMatching(vector<Vertex>* graph, size_t left_num, size_t right_num) {
graph_ = graph;
matching_ = new Vertex[right_num]; //matching_是右边顶点匹配的左边顶点，数组大小为right_num
fill(matching_, matching_ + right_num, NO_VERTEX);
visited_ = new bool[right_num]; //visited_标记右边顶点
match_num_ = 0;
for (size_t i = 0; i < left_num; i++) {
fill(visited_, visited_ + right_num, false);
if (dfs(i)) {
match_num_++;
}
}
free(matching_);
free(visited_);
return match_num_;
}
bool DFS::dfs(Vertex v) {
Vertex adj_v;
for (auto it = graph_[v].begin(); it != graph_[v].end(); it++) {
adj_v = *it;
if (!visited_[adj_v]) {
visited_[adj_v] = true;
if (matching_[adj_v] == NO_VERTEX || dfs(matching_[adj_v])) { //adj_v没有匹配或者adj_v的匹配可以找到其他匹配
matching_[adj_v] = v;
return true;
}
}
}
return false;
}
//BFS实现
class BFS : public Hungarian {
public:
virtual size_t maxMatching(vector<Vertex> * graph, size_t left_num, size_t right_num);
private:
Vertex * left_matching_;
Vertex * right_matching_;
queue<Vertex> vqueue_;
Vertex * pre_;
bool * visited_;
};
size_t BFS::maxMatching(vector<Vertex>* graph, size_t left_num, size_t right_num) {
left_matching_ = new Vertex[left_num]; //左边顶点匹配的顶点
fill(left_matching_, left_matching_ + left_num, NO_VERTEX);
right_matching_ = new Vertex[right_num]; //右边顶点匹配的顶点
fill(right_matching_, right_matching_ + right_num, NO_VERTEX);
pre_ = new Vertex[left_num]; //BFS中左边顶点的前驱
visited_ = new bool[right_num]; //右边顶点是否访问过
size_t result = 0;
for (Vertex i = 0; i < left_num; i++) { //遍历左边顶点
fill(visited_, visited_ + right_num, false); //初始化右边所有顶点没有访问过
vqueue_.push(i);
pre_[i] = NO_VERTEX; // i 没有前驱
Vertex front_v, adj_v;
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] != NO_VERTEX) { //adj_v已经匹配
vqueue_.push(right_matching_[adj_v]); //adj_v匹配到的顶点(左边)入队
pre_[right_matching_[adj_v]] = front_v; //记录前驱，即若right_matching_[adj_v]可以找到其他匹配，则front_v与adj_v匹配
}
else { //adj_v没有匹配
Vertex from = front_v, to = adj_v, tmp;
while (from != NO_VERTEX) {
tmp = left_matching_[from]; //from原来的匹配(右边顶点)
left_matching_[from] = to; //from 与 to 匹配
right_matching_[to] = from; //from 与 to 匹配
//from找到匹配，则pre_[from]与from原来的匹配即tmp匹配，更新from与to进入下次循环, \
若from之前并没有匹配，则pre_[from]为NO_VERTEX，下一次循环就会退出
from = pre_[from];
to = tmp;
}
while (!vqueue_.empty()) vqueue_.pop(); //清空队列
goto NEXT;
} //else
} //if
} //for
} //while
NEXT:
if (left_matching_[i] != NO_VERTEX) result++;
} //for
free(left_matching_);
free(right_matching_);
free(pre_);
free(visited_);
return result;
}
int main() {
unsigned int n, m, e;
scanf("%u %u %u", &n, &m, &e);
vector<Vertex> * graph = new vector<Vertex>[n];
Vertex u, v;
for (size_t i = 0; i < e; i++) {
scanf("%u %u", &u, &v);
if (u > n || v > m) continue;
u--; v--;
graph[u].push_back(v);
}
Hungarian * hungarian;
//hungarian = new DFS();
hungarian = new BFS();
unsigned int max_matching = hungarian->maxMatching(graph, n, m);
printf("%u", max_matching);
for (size_t i = 0; i < n; i++)
vector<Vertex>().swap(graph[i]);
delete hungarian;
return 0;
}