# 高阶扩展：二分关联图上的欧拉平衡 ## 本节目标 把“每个序列左右各一半、每个数值左右出现次数也相等”转成二分图每个点入度等于出度，并用欧拉回路一次满足两族约束。 ## 前置知识与课前自测 前置：二分关联图、无向欧拉回路。 1. 一次元素出现同时属于哪两个对象？ 2. 若把一次出现视作边，序列内左右平衡对应哪个点的度数条件？ 3. 欧拉回路沿行走方向定向后，每点入度和出度有何关系？
答案 1. 它所在的序列，以及它的数值。 2. 序列节点。 3. 相等；每次进入必有一次离开。
## 问题动机 逐数组均分和逐数值均分分别很容易，但一次出现同时影响两边配额，独立贪心会互相破坏。关联图把一次决策变成连接两种配额节点的一条边。 ## 精选例题：Fair Share ### 来源与题意 - VJudge：[CodeForces-1634E](https://vjudge.net/problem/CodeForces-1634E) - 原题：[Codeforces 1634E](https://codeforces.com/problemset/problem/1634/E) - 难度：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$。 ## 实现指南、核心伪代码与附件 ```text 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 实现](../../参考实现/07-二分图/CodeForces-1634E.cpp) ## 扩展与联系 “把边分成两类，使每点两类度数相等”与欧拉定向等价；本题的二分性只负责赋予方向 L/R 的统一语义，欧拉平衡本身适用于一般偶度多重图。 ## 实现边界与复盘 - 相同数值可在同一数组重复，关联图因此是多重图；必须按边编号访问。 - 只让每个数组交替写 `LRLR...` 不保证同一数值全局平衡；只按每个值配对又不保证数组配额。 - 若某些数组长度为奇数，连序列节点都出现奇度，欧拉充要条件仍能判无解。 - 若 L、R 需要按权重相等而非出现次数相等，入出度平衡不再表达目标。 ## 总结与自检 为什么数值总出现次数为偶数既必要又充分？为何沿欧拉回路定向能同时平衡数组节点和数值节点？ ## 课后训练建议 先在纸上画两个数组、三个数值的关联图并沿欧拉回路标方向；卡 20 分钟后看 Hint 3。复盘时写清“边的两端分别代表哪两种配额”。