UVa 13005 Blood Groups

题目描述

地球上的血型系统由 $2$ 个等位基因决定，有 $4$ 种血型。现考虑一种外星生命，其每个个体有 $N$ 位父母、$N$ 个等位基因、$N$ 种不同的抗原类型（编号为 $1$ 到 $N$）。等位基因可以是这 $N$ 种抗原类型中的任意一种，也可以是不表达任何抗原的 “$\text{O}$” 类型（即无抗原）。一个个体的血型由其所有非 $\text{O}$ 等位基因对应的抗原集合决定，若所有等位基因均为 $\text{O}$，则血型为空（$\text{O}$ 型）。

给定 $N$ 位父母的血型（每位父母的血型给出其含有的抗原集合），以及 $Q$ 个待查询的血型（每个查询也是一个抗原集合）。对于每个查询，需要判断：是否存在一种方式，从每位父母的等位基因组合中分别选出一个等位基因传递给后代，使得后代的血型恰好等于该查询集合。

输入格式

输入包含多个测试用例，每个测试用例格式如下：

• 第一行包含两个整数 $N$ 和 $Q$，分别表示父母个数（也等于等位基因个数和抗原种类数）和查询个数，满足 $1\le N\le 100$，$1\le Q\le 40$。
• 接下来 $N$ 行，每行描述一位父母的血型。每行以整数 $B$ 开头（$0\le B\le N$），表示该父母具有的抗原种类数，随后 $B$ 个互不相同的整数 $C_1,C_2,\dots ,C_B$（$1\le C_i\le N$），表示抗原类型编号。
• 接下来 $Q$ 行，每行描述一个查询血型。格式与父母血型相同：先给出 $B$，再给出 $B$ 个抗原编号。

输入以 $\text{EOF}$ 结束。

输出格式

对于每个测试用例，按照查询顺序输出 $Q$ 行，每行一个字符 Y 或 N，表示该查询血型是否可能在给定父母的后代中出现。

样例

输入

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

输出

N
Y
N
Y
N
Y
N
N

题目分析

本题是一个遗传可行性判定问题。关键点在于，每位父母的等位基因组合中，除了明确的抗原类型外，还可以存在 “$\text{O}$” 类型（即不表达抗原）。因此，一位父母可以传递给后代的非 $\text{O}$ 抗原类型，必须属于其血型集合；同时，该父母也可以选择传递 $\text{O}$ 类型，相当于不贡献任何抗原。

对于后代来说，它从 $N$ 位父母各继承一个等位基因，共 $N$ 个等位基因。后代的血型是这些等位基因中所有非 $\text{O}$ 类型的集合。因此，查询血型 $T$ 可行的充要条件是：存在一种从每位父母中选择一个等位基因的方式，使得所有被选中的非 $\text{O}$ 抗原恰好组成集合 $T$。

由于每位父母至多贡献一个非 $\text{O}$ 抗原（因为每位父母只传递一个等位基因），且每个抗原只要在集合 $T$ 中，就必须被至少一位父母贡献。至于那些没有贡献抗原的父母，他们只需传递 $\text{O}$ 类型即可，不会引入额外抗原。因此，问题转化为：能否用 $N$ 位父母（每人最多匹配一个抗原）去覆盖查询集合 $T$ 中的所有抗原，且每位父母只能匹配其血型中含有的抗原。

这正是二分图匹配问题：左侧是 $N$ 位父母，右侧是查询集合 $T$ 中的抗原，若父母含有某抗原，则连边，求最大匹配。若最大匹配数等于 $|T|$，则说明查询中每个抗原都能被至少一个父母覆盖，其余父母传递 $\text{O}$ 类型，后代血型恰为 $T$。

特别地，当 $|T|=0$（即 $\text{O}$ 型血）时，所有父母必须都能传递 $\text{O}$ 类型。一位父母能否传递 $\text{O}$ 类型，取决于其等位基因组合中是否至少有一个位置可以取 $\text{O}$。等价地，若父母的血型集合大小小于 $N$，则其组合中必有至少一个 $\text{O}$ 位置，可以传递 $\text{O}$；若血型集合大小等于 $N$，则所有位置都必须填满不同抗原，无法提供 $\text{O}$。因此，$\text{O}$ 型血可行当且仅当每位父母的血型大小均小于 $N$。

解题思路

建模为二分图匹配

对于每个查询，我们独立判断：

这里，父母侧抗原和子代侧抗原虽然编号相同，但为了网络结构清晰，我们将其分为两层，中间通过“相同抗原”的边连接。这样做的目的是限制每个抗原被匹配的次数，并且使得匹配关系从父母流经抗原再到汇点，符合二分图匹配的本质。

为什么 $\text{O}$ 型血单独处理

当 $B=0$ 时，右侧没有抗原节点，最大流只能为 $0$，但 $0$ 是否等于 $B$（即 $0$）总是成立，这会导致所有父母都能贡献 $\text{O}$ 的误判。实际上，若某父母血型大小为 $N$，则它无法贡献 $\text{O}$，因此必须单独检查。

复杂度分析

每个查询需要建图并跑一次最大流（$\text{Dinic}$ 算法）。图的大小：左侧 $N$ 个父母节点，父母侧抗原数不超过 $N$（因为抗原类型只有 $1$ 到 $N$），子代侧抗原数为 $B$（$B\le N$），总节点数 $O(N)$。边数：源点到父母 $N$ 条，父母到父母侧抗原最多 $N^2$ 条，父母侧到子代侧最多 $N^2$ 条，子代侧到汇点 $B$ 条，总边数 $O(N^2)$。由于 $N\le 100$，$\text{Dinic}$ 每次查询均可在微秒级完成，总查询数 $Q\le 40$，完全可行。

代码实现

// Blood Groups
// UVa ID: 13005
// Verdict: Accepted
// Submission Date: 2026-06-22
// UVa Run Time: 0.340s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
struct Edge { int to, rev, cap; };
vector<vector<Edge>> g;
vector<int> level, it;
Dinic(int n) : g(n), level(n), it(n) {}
void addEdge(int v, int to, int cap) {
if (cap <= 0) return;
Edge a{to, (int)g[to].size(), cap};
Edge b{v, (int)g[v].size(), 0};
g[v].push_back(a);
g[to].push_back(b);
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), –1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto &e : g[v])
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
return level[t] >= 0;
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); ++i) {
Edge &e = g[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0, INF = 1e9;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (true) {
int f = dfs(s, t, INF);
if (!f) break;
flow += f;
}
}
return flow;
}
};

bool feasibleForQuery(const vector<set<int>>& parents, const vector<int>& query) {
int N = parents.size();
int B = query.size();

// 查询为空（O型）：所有父母必须能贡献O（即血型大小<N）
if (B == 0) {
for (int i = 0; i < N; ++i)
if ((int)parents[i].size() == N) return false;
return true;
}

// 收集父母侧所有抗原（去重）
set<int> parentSet;
for (int i = 0; i < N; ++i)
for (int x : parents[i]) parentSet.insert(x);
vector<int> parentAntigens(parentSet.begin(), parentSet.end());
int PA = parentAntigens.size();

// 节点编号
int S = 0;
int parentStart = 1;
int parentAntigenStart = parentStart + N;
int childAntigenStart = parentAntigenStart + PA;
int T = childAntigenStart + B;
int V = T + 1;
Dinic din(V);

// 源点 -> 每位父母，容量1
for (int i = 0; i < N; ++i)
din.addEdge(S, parentStart + i, 1);

// 父母 -> 父母侧抗原（若父母拥有该抗原）
for (int i = 0; i < N; ++i)
for (int j = 0; j < PA; ++j)
if (parents[i].count(parentAntigens[j]))
din.addEdge(parentStart + i, parentAntigenStart + j, 1);

// 父母侧抗原 -> 子代侧抗原（相同抗原）
for (int j = 0; j < PA; ++j)
for (int k = 0; k < B; ++k)
if (parentAntigens[j] == query[k])
din.addEdge(parentAntigenStart + j, childAntigenStart + k, 1);

// 子代侧抗原 -> 汇点，容量1（每个抗原只需被覆盖一次）
for (int k = 0; k < B; ++k)
din.addEdge(childAntigenStart + k, T, 1);

int flow = din.maxFlow(S, T);
return flow == B;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, Q;
while (cin >> N >> Q) {
vector<set<int>> parents(N);
for (int i = 0; i < N; ++i) {
int B;
cin >> B;
for (int j = 0; j < B; ++j) {
int c;
cin >> c;
parents[i].insert(c);
}
}
for (int q = 0; q < Q; ++q) {
int B;
cin >> B;
vector<int> query(B);
for (int i = 0; i < B; ++i) cin >> query[i];
cout << (feasibleForQuery(parents, query) ? 'Y' : 'N') << '\\n';
}
}
return 0;
}

优化实现（匈牙利算法）

// Blood Groups
// UVa ID: 13005
// Verdict: Accepted
// Submission Date: 2026-06-22
// UVa Run Time: 0.200s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

bool canMatch(const vector<set<int>>& parents, const vector<int>& query) {
int N = parents.size();
int B = query.size();

// 查询为空（O型）：所有父母必须能贡献O（即血型大小<N）
if (B == 0) {
for (int i = 0; i < N; ++i)
if ((int)parents[i].size() == N) return false;
return true;
}

// 建立二分图：左部父母(0..N-1)，右部查询抗原(0..B-1)
vector<vector<bool>> adj(N, vector<bool>(B, false));
for (int i = 0; i < N; ++i)
for (int j = 0; j < B; ++j)
if (parents[i].count(query[j]))
adj[i][j] = true;

// 匈牙利算法
vector<int> matchR(B, –1);
function<bool(int, vector<bool>&)> dfs = [&](int u, vector<bool>& seen) -> bool {
for (int v = 0; v < B; ++v) {
if (adj[u][v] && !seen[v]) {
seen[v] = true;
if (matchR[v] == –1 || dfs(matchR[v], seen)) {
matchR[v] = u;
return true;
}
}
}
return false;
};

int matches = 0;
for (int u = 0; u < N; ++u) {
vector<bool> seen(B, false);
if (dfs(u, seen)) ++matches;
}
return matches == B;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, Q;
while (cin >> N >> Q) {
vector<set<int>> parents(N);
for (int i = 0; i < N; ++i) {
int B;
cin >> B;
for (int j = 0; j < B; ++j) {
int c;
cin >> c;
parents[i].insert(c);
}
}
for (int q = 0; q < Q; ++q) {
int B;
cin >> B;
vector<int> query(B);
for (int i = 0; i < B; ++i) cin >> query[i];
cout << (canMatch(parents, query) ? 'Y' : 'N') << '\\n';
}
}
return 0;
}

总结

本题的核心是将遗传可行性问题巧妙地转化为二分图匹配（最大流），而无需显式处理复杂的等位基因组合。关键洞察在于：

• 每位父母至多贡献一个非 $\text{O}$ 抗原，而 $\text{O}$ 抗原相当于“不匹配”，因此我们只需关注非 $\text{O}$ 抗原的覆盖。
• 查询血型中的每个抗原必须被至少一位父母覆盖，多余的父母可以贡献 $\text{O}$。
• 当查询为空时，需特殊判断所有父母是否都能贡献 $\text{O}$。

网络流模型将“父母→抗原→查询抗原”的匹配关系清晰表达，并通过最大流判断是否所有查询抗原均被覆盖。此解法简洁高效，适用于 $N\le 100$ 的规模。在解决此类组合覆盖问题时，将可行性转化为匹配或流问题是常用且有效的手段。