T28749: Top2招生工作
http://cs101.openjudge.cn/practice/28749/
小P作为一个学习过计算概论的贵校大一同学，参加了招生工作，负责整理今年考得比较好的同学们对于Top2两所学校的倾向，其中倾向于贵校的同学标记为“红色”，倾向于隔壁的同学标记为“紫色”，没有倾向的同学标记为“白色”。
小P进入招生组后了解到，招生组中靠谱的志愿者学长学姐已经在考前做好了招生的准备工作：每一位志愿者和一位或者多位考得比较好的同学建立了良好的联系，但是因为贵校志愿者数量有限，每一位考得比较好的同学至多和两位志愿者建立了良好的联系。
小P在接受招生组培训时，知道了招生中的重要特点：
《联系不上》：在出分后，考得比较好的同学只会和建立了良好联系的志愿者进行有效沟通
《懒惰的贵校同学》：一次有效沟通必须由志愿者发起，并且因为贵校志愿者比较懒，所以会一次性和所有具有良好联系的同学沟通
《丰俭由人》：志愿者可以进行若干次有效沟通，也可以偷懒摸鱼不沟通
《独自输出》：隔壁因为某些因素，在今年的招生中采取不作为策略，因此同学倾向的改变仅取决于贵校志愿者的有效沟通
每次有效沟通的效果如下：
- 《过犹不及》：原本就是“红色”倾向的同学会因为厌烦，一怒之下转变为“紫色”倾向
- 《拉拢中间派》：原本是“白色”倾向的同学会感受到贵校的热情，转变为“红色”倾向
- 《摇摆不定》：原本是”紫色“倾向的同学受到贵校的感召，决定转变为”白色“倾向，开始两边摇摆
招生组知道小P是学习过算法的大佬，于是将安排每一位志愿者有效沟通次数的重任交给了小P，希望能够用最少的总有效沟通次数，实现将所有考得比较好的同学倾向变为“红色”。
输入
输入的第一行包含两个整数n和m，其中n（1 <= n <= 2*10^5）是考得比较好的同学的数量，同学编号从1到n；m（0 <= m <= 2n）是志愿者的数量。
输入的第二行包含是一个由n个字符组成的字符串，这些字符是R,P,W中的一种(R代表倾向为红色，P代表倾向为紫色，W代表倾向为白色)，字符串中第i个字符，就代表了第i位同学最初的倾向。
接下来的m行，描述的是与每一位志愿者建立了良好联系的同学的信息：每一行以一个整数k（1 <= k <= n）开始，代表了与这位志愿者建立良好联系的同学数量，之后跟着k个不同的整数，代表了这些同学的编号。每一位同学至多和两个志愿者建立了良好联系。
输出
如果可以实现将所有考得比较好的同学倾向变为“红色”，则输出一个整数，即所需要的最少总有效沟通次数；如果不能够实现，则输出"impossible"。
样例输入
sample1 input:
8 6
PWRWRRRP
2 1 4
1 2
4 4 5 6 7
3 5 6 7
1 8
1 8
sample1 output:
8样例输出
sample2 input:
4 3
RPWR
2 1 2
2 2 3
2 3 4
sample2 output:
impossible提示
Recursion, 洪水填充 , 1100
Python程序常用的优化有三个：sys.setrecursionlimit(1<<30)、@lru_cache(maxsize = None)、sys.stdin.read。前两个主要是解决递归程序爆栈和重复计算子问题，后一个解决输入数据太多的问题。同学可以使用其中的一个或多个来优化程序。
来源
2024 TA-Xjk
一、题意概括
每个学生属于三种类型之一：
R（红） → 0P（蓝） → 1W（白） → 2
每个学生最多可以报名两个志愿（即两个“志愿者/招生点”）。 每个志愿者也可以被多个学生报考。
题目给出的约束是： 对每个学生 i：
- 若他报了两个志愿者
v1, v2，则有一个约束方程： - 若他只报了一个志愿者
v，则： - 若他一个志愿都没报，则必须是
R类型（即a_i = 0）。
目标：找到所有志愿者的取值（0,1,2），使所有方程成立，并使志愿者的值之和最小（即总代价最小）。
二、转化为图问题
- 志愿者是节点；
- 学生提供了约束方程；
- 每个学生对应一条或多条边：
| 学生类型 | 志愿个数 | 对志愿者约束 |
|---|---|---|
| 0 个志愿 | — | 若非R，则不可能 |
| 1 个志愿 | 1 | x_v = (-a_i) mod 3 → 志愿者取定值 |
| 2 个志愿 | 2 | x_u + x_v = (-a_i) mod 3 → 志愿者间关系 |
于是我们构建志愿者图：
- 边
(u,v,b)表示：x_u + x_v ≡ b (mod3)； - 节点可能有固定值（来自单志愿学生）。
三、算法步骤
- 读入学生与志愿者信息，转换成数字（R=0, P=1, W=2）。
- 检测无志愿学生：若不是R，则直接
impossible。 - 建立志愿者图：
- 对双志愿学生，加边；
- 对单志愿学生，记录节点的固定值。
- 检测矛盾固定值（同一志愿者被要求多个不同固定值）。
- 在志愿者图上进行 BFS/DFS 连通分量遍历：
- 若分量内有固定点 → 以这些为根进行值传播；
- 若没有固定点 → 任选一个节点为根，尝试 3 种起始值（0/1/2），选出合法且总代价最小的方案；
- 若出现冲突（方程不成立）→
impossible。
- 累加每个分量的最小代价。
- 输出总代价。
四、复杂度分析
- 建图：O(n + m)
- BFS/DFS：O(m + n)
- 每个分量最多尝试 3 次传播 总体复杂度 O((n + m) * 3) ≈ O(n + m)，可轻松通过。
✅ 带中文注释的完整代码
import sys
from collections import deque, defaultdict
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
# === 输入阶段 ===
n, m = map(int, input().split())
s = input().strip()
# R=0, P=1, W=2
enc = {'R':0, 'P':1, 'W':2}
a = [enc[ch] for ch in s]
# 每个学生的志愿列表（0-index）
stu = [[] for _ in range(n)]
# 每个志愿者对应的学生
vol = [[] for _ in range(m)]
for vid in range(m):
parts = list(map(int, input().split()))
k = parts[0]
for x in parts[1:]:
x0 = x-1
stu[x0].append(vid)
vol[vid].append(x0)
# === 基本合法性检测 ===
for i in range(n):
if not stu[i] and a[i] != 0:
print("impossible")
sys.exit(0)
# === 建立志愿者图 ===
# 对于双志愿学生，增加一条边 (v1,v2,b)
# 对于单志愿学生，记录该志愿者固定值 b
adj = [[] for _ in range(m)]
fixed_constraints = defaultdict(list) # vid -> 期望值列表
for i in range(n):
vs = stu[i]
if len(vs) == 2:
v1, v2 = vs
b = (-a[i]) % 3
adj[v1].append((v2, b))
adj[v2].append((v1, b))
elif len(vs) == 1:
v = vs[0]
b = (-a[i]) % 3
fixed_constraints[v].append(b)
# === 检查固定值冲突 ===
for v, lst in fixed_constraints.items():
first = lst[0]
for val in lst:
if val % 3 != first % 3:
print("impossible")
sys.exit(0)
fixed_value = {v: lst[0] % 3 for v, lst in fixed_constraints.items()}
# === BFS 遍历志愿者图 ===
visited = [False]*m
total_cost = 0
# 辅助函数：给定初始根节点赋值，传播约束
def try_with_roots(root_assignments):
assigned = {}
dq = deque()
for k, vv in root_assignments.items():
assigned[k] = vv % 3
dq.append(k)
while dq:
u = dq.popleft()
xu = assigned[u]
for (w, b) in adj[u]:
exp = (b - xu) % 3
if w in assigned:
if assigned[w] != exp:
return None # 冲突
else:
assigned[w] = exp
dq.append(w)
return assigned
# === 处理所有连通分量 ===
for v_start in range(m):
if visited[v_start] or not vol[v_start]:
visited[v_start] = True
continue
# 收集该连通分量所有节点
comp_nodes = []
q = deque([v_start])
visited[v_start] = True
while q:
u = q.popleft()
comp_nodes.append(u)
for (w, _) in adj[u]:
if not visited[w]:
visited[w] = True
q.append(w)
# 若该分量内有固定值，直接传播
comp_fixed = {u: fixed_value[u] for u in comp_nodes if u in fixed_value}
if comp_fixed:
res = try_with_roots(comp_fixed)
if res is None:
print("impossible")
sys.exit(0)
# 未被约束的节点可设为0以最小化代价
for u in comp_nodes:
if u not in res:
res[u] = 0
total_cost += sum(res[u] for u in comp_nodes)
continue
# 否则，尝试 root=0,1,2 三种情况
root = comp_nodes[0]
best = None
for r in range(3):
res = try_with_roots({root: r})
if res is None:
continue
for u in comp_nodes:
if u not in res:
res[u] = 0
cost = sum(res[u] for u in comp_nodes)
if best is None or cost < best:
best = cost
if best is None:
print("impossible")
sys.exit(0)
total_cost += best
# === 输出结果 ===
print(total_cost)💡 核心思路总结
- 本题实质是一个 模 3 线性方程系统；
- 志愿者为变量，学生为约束；
- 每个连通分量独立求解；
- 有固定点的分量直接确定；
- 无固定点的分量需尝试三种起点；
- 取最小代价（即志愿者取值之和最小）。
💡 题目理解与建模
题目看似描述招生故事，实际上是一个模 3 的线性方程系统 + 连通分量最小化问题。
一、状态变化规律（核心）
每个学生有三种状态：
- R（红）= 0
- P（紫）= 1
- W（白）= 2
一次“沟通”操作会让志愿者联系到的所有学生的状态发生如下变化：
| 初始 | 沟通后 |
|---|---|
| R(0) | P(1) |
| P(1) | W(2) |
| W(2) | R(0) |
即：状态值 +1（mod 3）
二、志愿者变量定义
令第
对某个学生
（要求最终为红色，即状态值为 0）
因此：
三、根据学生的志愿者数构造约束
✅ 情况 1：学生有两个志愿者
得到一条 志愿者之间的边：
即：在志愿者图中添加一条带权边 (u,v,b)。
✅ 情况 2：学生只有一个志愿者
得到一条 固定约束：
即：该志愿者的值被固定。
❌ 情况 3：学生没有志愿者
若他不是红色，则永远无法变红，直接输出 impossible。
四、问题转化为图问题
我们得到一个 带模约束的图：
- 节点：志愿者
- 边：来自两个志愿者共联一个学生的约束
- 节点固定值：来自单志愿者学生
- 每个连通分量可以独立求解
任务：
- 判断是否存在冲突（mod 3 矛盾）
- 若存在多种可行赋值，选取沟通次数之和最小的方案（每个志愿者的沟通次数是 0/1/2）
五、连通分量求解逻辑
- 若该分量中存在固定志愿者值，则从它出发 BFS 推导所有节点的值。若出现矛盾 → impossible。
- 若该分量没有固定志愿者：
- 任意选一个志愿者为根，尝试令其取值 0、1、2；
- 每种情况 BFS 推导；
- 若冲突则丢弃；
- 在所有可行方案中选总沟通次数最小的方案。
最终把每个分量的最优解相加。
✅ AC 代码（带详细中文注释）
import sys
from collections import deque
def main():
# ---------- 快速读入 ----------
data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
s = next(it).decode()
# ---------- 编码倾向 ----------
enc = {'R':0, 'P':1, 'W':2}
a = [enc[ch] for ch in s]
# ---------- 建立学生和志愿者关系 ----------
stu = [[] for _ in range(n)] # 每个学生对应的志愿者
vol = [[] for _ in range(m)] # 每个志愿者对应的学生
for vid in range(m):
k = int(next(it))
for _ in range(k):
x = int(next(it)) - 1
stu[x].append(vid)
vol[vid].append(x)
# ---------- 检查无志愿者的学生 ----------
for i in range(n):
if not stu[i] and a[i] != 0:
print("impossible")
return
# ---------- 构造志愿者之间的约束图 ----------
adj = [[] for _ in range(m)] # 邻接表，存储 (邻居, b)
fixed_value = [-1] * m # 某志愿者的固定值（若有单志愿者学生约束）
for i in range(n):
vs = stu[i]
if len(vs) == 2:
v1, v2 = vs
b = (-a[i]) % 3
adj[v1].append((v2, b))
adj[v2].append((v1, b))
elif len(vs) == 1:
v = vs[0]
b = (-a[i]) % 3
if fixed_value[v] == -1:
fixed_value[v] = b
elif fixed_value[v] != b:
print("impossible")
return
# len==0 情况前面已排除
# ---------- 初始化 ----------
visited = [False] * m
assigned = [-2] * m # 志愿者沟通次数：-2=未赋值，0/1/2=次数 mod3
total_cost = 0
# ---------- 逐个连通分量处理 ----------
for v in range(m):
if visited[v]:
continue
if not vol[v]: # 没关联学生的志愿者，跳过
visited[v] = True
continue
# BFS 收集该连通分量内所有志愿者
comp = []
dq = deque([v])
visited[v] = True
while dq:
u = dq.popleft()
comp.append(u)
for w, _ in adj[u]:
if not visited[w]:
visited[w] = True
dq.append(w)
# 找出该分量内的固定节点
comp_fixed_nodes = [u for u in comp if fixed_value[u] != -1]
# ---------- BFS传播函数 ----------
def propagate_init(init_list):
touched = [] # 记录被修改过的志愿者，方便回滚
q = deque()
for (uu, val) in init_list:
assigned[uu] = val
touched.append(uu)
q.append(uu)
# 传播约束：x_v = (b - x_u) mod 3
while q:
uu = q.popleft()
xuu = assigned[uu]
for vv, b in adj[uu]:
need = (b - xuu) % 3
cur = assigned[vv]
if cur == -2:
assigned[vv] = need
touched.append(vv)
q.append(vv)
elif cur != need:
# 冲突 -> 回滚并返回失败
for t in touched:
assigned[t] = -2
return None
return touched # 返回成功修改的节点列表
# ---------- 情况 1：该分量有固定志愿者 ----------
if comp_fixed_nodes:
init_list = [(u, fixed_value[u]) for u in comp_fixed_nodes]
touched = propagate_init(init_list)
if touched is None:
print("impossible")
return
# 未连接的节点设为0
comp_cost = 0
for u in comp:
if assigned[u] == -2:
assigned[u] = 0
comp_cost += assigned[u]
total_cost += comp_cost
continue
# ---------- 情况 2：该分量无固定志愿者 ----------
root = comp[0]
best_cost = None
best_touched = None
# 尝试根节点为 0,1,2 的三种情况
for r in (0,1,2):
touched = propagate_init([(root, r)])
if touched is None:
continue
# 未赋值的节点设为0
for u in comp:
if assigned[u] == -2:
assigned[u] = 0
touched.append(u)
cost = sum(assigned[u] for u in comp)
if best_cost is None or cost < best_cost:
best_cost = cost
best_touched = list(touched)
# 回滚，为下次尝试清空状态
for t in touched:
assigned[t] = -2
if best_cost is None:
print("impossible")
return
# 重新传播最优方案并保留结果
propagate_init([(root, 0)])
for u in comp:
if assigned[u] == -2:
assigned[u] = 0
total_cost += best_cost
# ---------- 输出最小总沟通次数 ----------
print(total_cost)
if __name__ == "__main__":
main()🧠 思路总结（简洁版）
| 步骤 | 含义 | 操作 |
|---|---|---|
| 1 | 把每个学生的状态转为数字 0/1/2 | R→0, P→1, W→2 |
| 2 | 根据学生连接的志愿者数，构造模 3 方程 | 两志愿者→等式；一志愿者→固定值 |
| 3 | 构造志愿者图 | 每个志愿者是节点，边权表示模 3 关系 |
| 4 | 分别处理每个连通分量 | BFS 传播解模 3 线性系统 |
| 5 | 若有多解，枚举根取最小代价 | root=0/1/2 三种方案 |
| 6 | 汇总最小沟通次数 | 输出结果 |
✅ 复杂度分析
| 部分 | 复杂度 |
|---|---|
| 构建图 | O(n + m) |
| BFS传播 | O(n + m) |
| 每分量枚举3种root | 最多 3×O(节点数) |
| 总复杂度 | O(n + m) （常数极小） |
内存占用也为 O(n + m)，完全可通过 2×10⁵ 级别数据。
如果你愿意，我还可以帮你画一张 “志愿者-学生图 + 状态变化 mod3 动态示意图”（比如样例输入），帮助直观理解 “x_u + x_v ≡ b (mod 3)” 是如何传播的。是否需要？