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
| #include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 500;
const int M = 1e5 + 10;
int head[N], ver[M], edge[M], Next[M], d[N];
int tot, maxflow;
int s, t;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs() {
memset(d, 0, sizeof(d));
queue<int> q;
q.push(s); d[s] = 1;
while(q.size()) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = Next[i]) {
if(edge[i] && !d[ver[i]]) {
q.push(ver[i]);
d[ver[i]] = d[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for(int i = head[x]; i && rest; i = Next[i]) {
if(edge[i] && d[ver[i]] == d[x] + 1) {
k = dinic(ver[i], min(rest, edge[i]));
if(!k) d[ver[i]] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> m >> n;
tot = 1;
s = 0;
t = n + 1;
for(int i = 1; i <= m; ++i) add(s, i, 1);
for(int i = m + 1; i <= n; ++i) add(i, t, 1);
int u, v;
while(cin >> u >> v) {
if(u == -1 && v == -1) break;
add(u, v, 1);
}
int flow = 0;
while(bfs()) {
while(flow = dinic(s, inf)) {
maxflow += flow;
}
}
if(maxflow == 0) {
cout << "No Solution!" << endl;
return 0;
}
cout << maxflow << endl;
for(int i = 1; i <= m; ++i) {
for(int j = head[i]; j; j = Next[j]) {
if(ver[j] != s && edge[j] == 0 && edge[j ^ 1] == 1) {
cout << i << " " << ver[j] << endl;
}
}
}
return 0;
}
|