题解归档 - cf600F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf600F
• 本地来源：problems/cf600F/idea.md
• 题目链接：https://codeforces.com/contest/600/problem/F
• 原始标题：CF600F — Edge coloring of bipartite graph

思路

CF600F — Edge coloring of bipartite graph

题意

给定二分图（左部 a、右部 b、边 m），给每条边染色，使同一顶点的相邻边颜色不同。求最少颜色数，并输出一种方案（边按输入顺序输出颜色）。

结论

二分图的边色数（chromatic index）等于最大度数 Δ（König 线着色定理）。因此答案 c = max(deg)。

构造

按输入顺序逐条染色。维护 f[0][u][c] / f[1][v][c]：左点 u（右点 v）在颜色 c 上连接的右（左）邻点。

对边 (u,v)：

• t0 = 左点 u 的最小空闲色；t1 = 右点 v 的最小空闲色。
• 若 t0 == t1，直接染 t0。
• 否则沿 交替路径 DFS：先给 (u,v) 染 t0，把右点 v 上原占 t0 的边改染 t1，依此类推；二分图保证链有限且不会成环。

答案 c = max deg，由处理过程中 max(t0,t1) 得到。

朴素「两端都未用的最小色」贪心会 WA，必须用上述交替换色。

实现

• f[0][u][k] / f[1][v][k] 记录颜色 k 在左/右点的配对邻点；g[u][v] 存边号。
• dfs 沿交替链换色，均摊 O(n) 每条边，总 O(nm)。

样例

4 3 5
1 2 / 2 2 / 3 2 / 4 1 / 4 3

右点 2 度数为 3 → c=3。贪心得 1 2 3 1 2。

验证

• 样例 + WSL 对拍 500 组（stress_wsl.sh，Kali 离线时用 WSL 替代 stress.py）。

代码

来源：problems/cf600F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:18:13
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1005;
ll a,b,m,i,j,k,u,v,t0,t1,mxdeg;
ll f[2][maxn+5][maxn+5],g[maxn+5][maxn+5],c[maxn*100+5];
void dfs(ll a,ll b,ll x,ll y,ll now,ll pre){
    ll to=f[b][y][now];
    f[a][x][now]=y;
    f[b][y][now]=x;
    if(!to) f[b][y][pre]=0;
    else dfs(b,a,y,to,pre,now);
}
int main(){
    cin>>a>>b>>m;
    for(i=1;i<=m;i++){
        cin>>u>>v;
        g[u][v]=i;
        t0=1;
        while(f[0][u][t0]) t0++;
        t1=1;
        while(f[1][v][t1]) t1++;
        mxdeg=max(mxdeg,max(t0,t1));
        if(t0==t1){
            f[0][u][t0]=v;
            f[1][v][t0]=u;
        }else dfs(0,1,u,v,t0,t1);
    }
    cout<<mxdeg<<endl;
    for(i=1;i<=a;i++){
        for(j=1;j<=mxdeg;j++){
            if(f[0][i][j]) c[g[i][f[0][i][j]]]=j;
        }
    }
    for(i=1;i<=m;i++){
        if(i>1) cout<<" ";
        cout<<c[i];
    }
    cout<<endl;
    return 0;
}