高阶扩展：二分关联图上的欧拉平衡

本节目标

把“每个序列左右各一半、每个数值左右出现次数也相等”转成二分图每个点入度等于出度，并用欧拉回路一次满足两族约束。

前置知识与课前自测

前置：二分关联图、无向欧拉回路。

一次元素出现同时属于哪两个对象？
若把一次出现视作边，序列内左右平衡对应哪个点的度数条件？
欧拉回路沿行走方向定向后，每点入度和出度有何关系？

答案

1. 它所在的序列，以及它的数值。 2. 序列节点。 3. 相等；每次进入必有一次离开。

问题动机

逐数组均分和逐数值均分分别很容易，但一次出现同时影响两边配额，独立贪心会互相破坏。关联图把一次决策变成连接两种配额节点的一条边。

精选例题：Fair Share

来源与题意

VJudge：CodeForces-1634E
原题：Codeforces 1634E
难度：2400；考点：双重配额、关联多重图、欧拉定向

给 $m\le10^5$ 个偶数长度数组，总长度不超过 $2\times10^5$。把每次出现标为 L 或 R，使每个数组恰好一半为 L，并且 L、R 作为多重集完全相等；构造或判无解。

Hint 1

左侧建数组节点，右侧建离散化后的数值节点；每次出现是一条带原位置编号的边。

Hint 2

数组节点度数已为偶数。数值节点度数为该值总出现次数；奇数时为什么必无解？

Hint 3

所有点度数偶数时，每个连通分量都有欧拉回路。

Hint 4

沿欧拉回路给边定向；从数组指向数值记 L，反向记 R。

Observations、Editorial 与证明

L、R 多重集相等，等价于每个数值的出现中 L 与 R 数量相等；数组约束则要求每个数组节点也左右相等。这不是两个独立背包，而是每次出现同时消耗一条“数组配额”和一条“数值配额”。关联图把这两个归属保留在同一条边上。

必要性很直接：某数值总出现奇数次时无法均分。反之所有数值度数为偶数，加上题目保证的偶数数组长度，二分多重图每个点度数均偶；每个非空连通分量存在欧拉回路。

按回路行走方向给每条出现边定向。闭合欧拉游走在每个点每进入一次就离开一次，故入度等于出度。在数组节点，把出边记 L、入边记 R，数组内部各半；在数值节点方向语义相反，但仍一半边从数组指来、一半指回数组，所以该值在 L、R 中出现次数相等。每条边恰对应一个原位置，输出不漏不重。

离散化 $O(K\log K)$，Hierholzer $O(K)$，空间 $O(K)$，其中 $K\le2\times10^5$。

实现指南、核心伪代码与附件

for each occurrence at array i, position j, value x:
    add an indexed edge between array_node(i) and value_node(x)
if some value node has odd degree: output NO
for every nonempty component:
    run Hierholzer and orient each used edge along the tour
    array -> value means L; value -> array means R
write each edge label back to its original (i,j)

完整 GNU C++17 实现

扩展与联系

“把边分成两类，使每点两类度数相等”与欧拉定向等价；本题的二分性只负责赋予方向 L/R 的统一语义，欧拉平衡本身适用于一般偶度多重图。

实现边界与复盘

相同数值可在同一数组重复，关联图因此是多重图；必须按边编号访问。
只让每个数组交替写 LRLR... 不保证同一数值全局平衡；只按每个值配对又不保证数组配额。
若某些数组长度为奇数，连序列节点都出现奇度，欧拉充要条件仍能判无解。
若 L、R 需要按权重相等而非出现次数相等，入出度平衡不再表达目标。

总结与自检

为什么数值总出现次数为偶数既必要又充分？为何沿欧拉回路定向能同时平衡数组节点和数值节点？

课后训练建议

先在纸上画两个数组、三个数值的关联图并沿欧拉回路标方向；卡 20 分钟后看 Hint 3。复盘时写清“边的两端分别代表哪两种配额”。

04-高阶扩展-关联图欧拉平衡.md 4.4 KB Historie Surový