UVa 12880 - Book Club

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 N 個人的愛書俱樂部,他們會喜歡某些人的書,如果相互喜歡對方的書就可以進行交換,現在要問的是否每個人都能找到能夠交換的對象,讓每個人都獲得新書。

如果 A -> B, B -> C, C -> A,那麼他們可以環狀地交換新書。

Sample Input

1
2
3
4
5
6
7
8
9
10
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5

Sample Output

1
YES

Solution

每個人只能找一個對象進行交換,找二分圖的 perfect matching。

二分圖中左側是每個人,右側是想要交換的對象,兩邊的個數都是 N。匹配完會找到數個環狀,這就是最後的交換情況。然而由於點數很多,用匈牙利算法可以減枝來加快,每一次擴充路徑都必須得成功。如果使用 maxflow,則盡可能減少邊的無效使用。

當然可以使用 maxflow 貪心預流、匈牙利貪心匹配過後,再套用算法,速度有可能會快上許多,以下的模板還真好用,減少無效使用於分層圖,所以速度快上很多。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;

const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
int v, cap, flow;
Edge *next, *re;
} Edge;
class MaxFlow {
public:
Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
void Init(int x) {
n = x, e = 0;
for (int i = 0; i < n; ++i) adj[i] = NULL;
}
void Addedge(int x, int y, int flow){
edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
edge[e].re = &edge[e+1], adj[x] = &edge[e++];
edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
edge[e].re = &edge[e-1], adj[y] = &edge[e++];
}
void Bfs(int v){
int front = 0, rear = 0, r = 0, dis = 0;
for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
level[v] = 0, ++lvCnt[0];
Q[rear++] = v;
while (front != rear){
if (front == r) ++dis, r = rear;
v = Q[front++];
for (Edge *i = adj[v]; i != NULL; i = i->next) {
int t = i->v;
if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
}
}
}
int Maxflow(int s, int t){
int ret = 0, i, j;
Bfs(t);
for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
i = s;
while (level[s] < n){
while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow))
arc[i] = arc[i]->next;
if (arc[i]){
j = arc[i]->v;
pre[j] = arc[i];
i = j;
if (i == t){
int update = INF;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
if (update > p->flow) update = p->flow;
ret += update;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
p->flow -= update, p->re->flow += update;
i = s;
}
}
else{
int depth = n-1;
for (Edge *p = adj[i]; p != NULL; p = p->next)
if (p->flow && depth > level[p->v]) depth = level[p->v];
if (--lvCnt[level[i]] == 0) return ret;
level[i] = depth+1;
++lvCnt[level[i]];
arc[i] = adj[i];
if (i != s) i = pre[i]->re->v;
}
}
return ret;
}
} g;

int main() {
int n, m, x, y;
while (scanf("%d %d", &n, &m) == 2) {
g.Init(2 * n + 2);
int source = 2 * n, sink = 2 * n + 1;
for (int i = 0; i < n; i++)
g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
for (int i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
g.Addedge(x, y + n, 1);
}

int matching = g.Maxflow(source, sink);
puts(matching == n ? "YES" : "NO");
}
return 0;
}
/*
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
*/