UVa 13005 - Blood groups

contents

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

Problem

還記得孟德爾遺傳法則嗎?從血型分成 A, B, AB, O 型四種,由三個遺傳因子 A, B, i 兩兩組合而成。而外星人突破孟德爾遺傳法則,由 $N$ 個遺傳因子 (不包含隱性因子 i) 決定表徵,並且一個子代會從 $N$ 個父代分別繼承一個遺傳因子。

現在給予在場 $N$ 個父代分別有哪些遺傳因子 (若沒有告知,則剩餘都是隱性因子 i),接下來會有 $Q$ 組詢問,問某一個遺傳因子組合是否可以被在場 $N$ 個父代組合而成。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2 1
2 2 1
1 2
0
3 4
1 1
2 2 3
0
1 3
3 2 1 3
2 1 2
2 3 2
4 3
4 2 1 3 4
4 2 1 3 4
1 1
1 2
1 3
2 2 1
0

Sample Output

1
2
3
4
5
6
7
8
N
Y
N
Y
N
Y
Y
N

Solution

每一個父代都提供一個遺傳因子,問最後能不能滿足所有匹配,顯而易見地是一題完美二分匹配。建造 source - 父代 - 遺傳因子 - sink。若某一組詢問需要父代提供遺傳因子 $x$,就去找尋有哪些父代可以提供遺傳因子,並且拉一條邊 父代 - 遺傳因子 x 流量為 1。隱性提供者特別判斷一下即可。

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
#include <bits/stdc++.h>
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, Q, B, x;
while (scanf("%d %d", &N, &Q) == 2) {
set< set<int> > S;
set<int> A[128];
for (int i = 0; i < N; i++) {
scanf("%d", &B);
for (int j = 0; j < B; j++) {
scanf("%d", &x);
A[i].insert(x);
}
if (B != N) A[i].insert(0);
}

for (int i = 0; i < Q; i++) {
int source = 2*N+2, sink = 2*N+3;
g.Init(2*N+5);

int used[128] = {};
for (int j = 0; j < N; j++) // parent
g.Addedge(source, j, 1);

scanf("%d", &B);
for (int j = 0; j < B; j++) {
scanf("%d", &x);
g.Addedge(N+x, sink, 1);
for (int k = 0; k < N; k++) {
if (A[k].count(x)) {
g.Addedge(k, N+x, 1);
used[k] = 1;
}
}
}

int allused = 1;
for (int j = 0; j < N; j++) {
if (A[j].count(0) && B != N)
used[j] = 1;
allused &= used[j];
}

if (!allused) {
puts("N");
continue;
}

int flow = g.Maxflow(source, sink);
puts(flow == B ? "Y" : "N");
}
}
return 0;
}