Vizing 定理
对于简单图 $G$:
$$\chi'(G) \le \Delta (G) + 1$$其中 $\chi'(G)$ 为图 $G$ 的边色数，即最少使用多少颜色可以为 $G$ 的边染色，使得相邻边彼此颜色不同。$\Delta (G)$ 是图的最大点度数。
二分图 Vizing 定理
特别的对于二分图我们有
$$\chi'(G) = \Delta (G) $$我们可以构造性的证明这个结论：
我们按顺序考虑每一条边 $<u, v>$，
令 $c_u$ 为 $u$ 作为端点的边没用用过的最小颜色编号（$1$ 开始），令 $c_v$ 为 $v$ 作为端点的边没用用过的最小颜色编号。
如果 $c_u = c_v$ 则我们直接将该颜色赋给边 $<u, v>$，否则我们假设 $c_u < c_v$ 然后把进行如下操作，
我们寻找一条以 $v$ 为起点的颜色按照 $c_u, c_v, c_u, c_v, \cdots$ 交替的增广路（这不会是一颗树，因为每个节点相邻的边彼此颜色不同），注意到此增广路一定不会过 $u$。因为图 $G$ 是一个二分图，则增广过程必然经过一条 $c_u$ 的边才能到达 $u$ 一侧的点，而如果到达 $u$ 这将与假设**$c_u$ 为 $u$ 作为端点的边没用用过的最小颜色编号**不符。
此时我们将整个增广路上的颜色 $c_u$ 与 $c_v$ 翻转，于是 $v$ 点的为端点的边也没有 $c_u$ 颜色的了。从而我们可以将新边染色为 $c_u$。
这里我们注意到 $c_u \le deg(u)$ 与 $c_v \le deg(v)$ 因此可以得到，所有用到的颜色都是少于 $\Delta (G)$ 的。
时间复杂度 ： 增广路上最多会有 $O(V)$ 个点，因此总复杂度为 $O(EV)$。
例题及代码
Educational Codeforces Round 2F
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
const int MV = 1005;
const int ME = 1e5 + 5;
int col[MV + MV][MV];
int id[MV + MV][MV];
int ans[ME];
void setcol(int u, int v, int c, int i) {
col[u][c] = v;
col[v][c] = u;
id[u][c] = i;
id[v][c] = i;
ans[i] = c;
}
void aug(int u, int lu, int lv) {
if (!col[u][lu]) {
col[u][lv] = 0;
return;
}
int v = col[u][lu];
int i = id[u][lu];
aug(v, lv, lu);
col[u][lu] = 0;
setcol(u, v, lv, i);
}
void solve() {
int a, b, m;
cin >> a >> b >> m;
int n = a + b;
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
v += a;
int lu = 1, lv = 1;
while (col[u][lu]) lu++;
while (col[v][lv]) lv++;
if (lu == lv) {
setcol(u, v, lu, i);
continue;
}
if (lu > lv) {
swap(u, v);
swap(lu, lv);
}
// lu < lv
aug(v, lu, lv);
setcol(u, v, lu, i);
}
int mx = 0;
for (int i = 0; i < m; i++) {
cmax(mx, ans[i]);
}
cout << mx << '\n';
for (int i = 0; i < m; i++) {
cout << ans[i] << (" \n"[i == m - 1]);
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: E. Wooden Game - Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)