解題區/解題區 - UVa

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;
}