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
这个问题可以通过图论和线性同余方程组来解决。
题目分析
状态转换：同学的倾向变化呈周期性：
。我们可以将颜色映射为数字： 。 沟通效果：每一次有效沟通相当于给该志愿者联系的所有同学的状态加 1（在模 3 意义下）。
目标：所有同学变为
（即状态 0）。 方程建立：
- 设志愿者
的沟通次数为 。 - 设同学
的初始状态为 。目标是 。 - 变换得：
。令 。
- 设志愿者
约束条件：
每个同学至多联系 2 位志愿者。
如果同学
联系 0 位：需满足 ，否则无法达成目标（impossible）。 如果同学
联系 1 位（志愿者 ）： 。这固定了 的值。 或 2 个相同的，也要丢进 fixed_constraints 桶里。
如果同学
联系 2 位（志愿者 ）： 。
解题思路
这是一个约束满足问题。我们可以将志愿者视为图中的节点，将联系两位志愿者的同学视为连接这两个节点的边。
- 组件分解：将所有志愿者按边（同学联系）划分为多个连通分量。
- 分量求解：对于每个连通分量：
- 如果有任何志愿者的次数
已经被单人联系的同学固定，则整个分量的所有节点次数都可以被唯一推导出来。 - 如果没有固定值，我们可以尝试将分量中的某个起始节点设为 0, 1, 或 2，分别推导出分量内其他节点的值。
- 如果有任何志愿者的次数
- 合法性校验：在推导过程中，必须检查所有边的约束是否满足（即
）。 - 代价最小化：对于每个合法的分配方案，计算
。在没有固定值的分量中，取三种尝试中代价最小的一个。 - 不可行判断：如果某个分量在所有尝试下都无法满足约束，或者单人固定值本身存在冲突，则输出
impossible。
python
import sys
def solve():
# 使用 sys.stdin.read().split() 快速读取大数据量
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
m = int(data[1])
s = data[2]
# 映射初始倾向到目标余数 b_i = -s_i mod 3
# R: 0 -> 0; P: 1 -> 2; W: 2 -> 1
mapping = {'R': 0, 'P': 2, 'W': 1}
b = [0] * (n + 1)
for i, char in enumerate(s):
b[i + 1] = mapping[char]
# 建立同学到志愿者的映射
student_vols = [[] for _ in range(n + 1)]
ptr = 3
for v_idx in range(1, m + 1):
k = int(data[ptr])
ptr += 1
for _ in range(k):
sid = int(data[ptr])
ptr += 1
student_vols[sid].append(v_idx)
# 构建图：边表示两个志愿者共同联系一名同学
adj = [[] for _ in range(m + 1)]
fixed = [None] * (m + 1)
for i in range(1, n + 1):
vols = student_vols[i]
bi = b[i]
if not vols:
if bi != 0:
print("impossible")
return
elif len(vols) == 1:
v = vols[0]
if fixed[v] is not None and fixed[v] != bi:
print("impossible")
return
fixed[v] = bi
else:
u, v = vols[0], vols[1]
if u == v:
# 特殊情况：同一志愿者联系两次，2*xu = bi mod 3 => xu = 2*bi mod 3
val = (2 * bi) % 3
if fixed[u] is not None and fixed[u] != val:
print("impossible")
return
fixed[u] = val
else:
adj[u].append((v, bi))
adj[v].append((u, bi))
visited = [False] * (m + 1)
assigned_vals = [None] * (m + 1)
total_ans = 0
# 用于 BFS 的辅助数组
q = [0] * (m + 1)
reset_list = [0] * (m + 1)
for i in range(1, m + 1):
if not visited[i]:
# 找到连通分量
comp = []
bfs_q = [i]
visited[i] = True
comp.append(i)
idx = 0
while idx < len(bfs_q):
u = bfs_q[idx]
idx += 1
for v, _ in adj[u]:
if not visited[v]:
visited[v] = True
bfs_q.append(v)
comp.append(v)
# 检查分量中是否有预设的固定值
start_node = -1
for node in comp:
if fixed[node] is not None:
start_node = node
break
def get_comp_cost(entry_node, entry_val):
"""
尝试为一个连通分量分配沟通次数。
entry_node: 起始志愿者编号
entry_val: 假设起始志愿者的沟通次数 (0, 1, 或 2)
"""
r_ptr = 0 # 记录本次尝试中修改了多少个节点，用于后续重置
h = t = 0 # BFS 队列的头指针和尾指针
# 初始化：给起始节点赋值，并入队
q[t] = entry_node
t += 1
assigned_vals[entry_node] = entry_val
# 记录修改：reset_list 存下修改过的志愿者编号，方便事后“擦除”
reset_list[r_ptr] = entry_node
r_ptr += 1
cost = entry_val # 累加当前分量内所有志愿者的总沟通次数
possible = True # 标记当前的 entry_val 假设是否合法
while h < t:
u = q[h] # 弹出队列头部的志愿者
h += 1
# 遍历与 u 共同联系一名同学的所有邻居 v
# target 是同学需要的总沟通次数 b_i，满足 xu + xv ≡ target (mod 3)
for v, target in adj[u]:
# 推导 v 应该进行的沟通次数：xv = (target - xu) % 3
required = (target - assigned_vals[u]) % 3
if assigned_vals[v] is not None:
# 冲突检查 1：如果 v 已经在本次搜索中赋过值了
# 检查已有的值是否和推导出来的 required 矛盾
if assigned_vals[v] != required:
possible = False
break
else:
# 冲突检查 2：检查推导出的值是否违背了该志愿者自身的“单人固定约束”
if fixed[v] is not None and fixed[v] != required:
possible = False
break
# 若无冲突，为志愿者 v 赋值并继续 BFS
assigned_vals[v] = required
reset_list[r_ptr] = v # 记录修改
r_ptr += 1
cost += required # 累加总沟通次数
q[t] = v # 将 v 入队
t += 1
if not possible: break # 如果发现冲突，提前退出循环
# === 关键性能优化：现场清理 ===
# 因为我们要尝试 0, 1, 2 三种起始值，每次尝试都会修改全局数组 assigned_vals。
# 为了不花时间去初始化整个大数组（2*10^5 长度），
# 我们只根据 reset_list 记录的索引，把修改过的地方变回 None。
for r in range(r_ptr):
assigned_vals[reset_list[r]] = None
# 如果推演成功（无冲突），返回总次数；否则返回无穷大
return cost if possible else float('inf')
if start_node != -1:
res = get_comp_cost(start_node, fixed[start_node])
if res == float('inf'):
print("impossible")
return
total_ans += res
else:
# 尝试三种起始值，取最小代价
c0 = get_comp_cost(comp[0], 0)
c1 = get_comp_cost(comp[0], 1)
c2 = get_comp_cost(comp[0], 2)
best = min(c0, c1, c2)
if best == float('inf'):
print("impossible")
return
total_ans += best
print(total_ans)
if __name__ == '__main__':
solve()一、题意概括
每个学生属于三种类型之一：
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)，可轻松通过。
✅ 带中文注释的完整代码
python
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 代码（带详细中文注释）
python
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)” 是如何传播的。是否需要？