CF600F Edge coloring of bipartite graph 题解

· · 题解

猜测

点染色判断二分图的方法想必大家都有所耳闻，那么边染色呢？

给出一个二分图，求最小边染色。

当看到最小边染色这几个字时，大胆猜测：

二分图的最小边染色结果等于点的最大度数。

相邻边颜色不同已经为此做下了铺垫：由于一个点的度数记录的是与这个点相连的边数，而这些边都相邻，不能是同一种颜色，所以猜测二分图的最小边染色结果等于点的最大度数。

证明：

设点的最大度数为 k，二分图的最小边染色结果为 ans。

显然，ans\geq k（最大度数为 k 说明最多有 k 条边相邻的情况）。

考虑构造一种染色方法：

对于任意一条边 (u,v)，设集合为点 u 连边的颜色集为 C1，点 v 连边的颜色集为 C2。

定义 {\rm{mex(S)}} 为不属于集合 S 的最小正整数。

若 {\rm{mex(C1)}}={\rm{mex(C2)}}：

即存在一种颜色使得集合 C1,C2 中都不包含并且最小。

直接用其将 (u,v) 染色。

若 {\rm{mex(C1)}}\ne{\rm{mex(C2)}}：

说明在集合 C2 中存在一种颜色等于 {\rm{mex(C1)}}。

找出这条边，设为 (v,w)，这条边的颜色等于 {\rm{mex(C1)}}。

将 (u,v) 强制染上 {\rm{mex(C1)}}，此时 (u,v) 与 (v,w) 颜色冲突。

将 (v,w) 的颜色转化为 {\rm{mex(C2)}}。

此时 (u,v) 与 (v,w) 颜色不冲突。

但是 (v,w) 可能与 (w,x) 颜色冲突，考虑循环使用如上方法解决。

设从 (u,v) 开始的循环到 (y,z) 结束，即 {\rm{mex(C1_y)}}={\rm{mex(C2_z)}}。

此时，从 (u,v) 开始的循环到 (y,z) 结束这个过程就相当于一条链。

由于此图是二分图，所以必定有一条边的两种颜色不冲突。

而其中的 \max(|C1|_ {\max},|C2|_ {\max})=k=ans。

构造完毕。

证毕。

发现链的长度最多为 a+b，遍历每条边，共 m 条，所以时间复杂度为：O((a+b)m)。

代码

代码中包含讲解：

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}

const int MAXN=2e3+5;
const int MAXM=1e5+5;
int a,b,m,u[MAXM],v[MAXM],in[MAXN];
int ans,color1,color2,color[MAXN][MAXN];

//color[i][j]=k表示(i,k)这条边的颜色为j

int main(){
    a=read(),b=read(),m=read();
    for(int i=1;i<=m;++i){
        u[i]=read(),v[i]=read();
        v[i]+=a;
        //将v[i]的大小计入总图中
        in[u[i]]++,in[v[i]]++;
        //统计度数
    }
    for(int i=1;i<=a+b;++i){
        ans=max(ans,in[i]);
        //寻找最大度数
    }
    for(int i=1;i<=m;++i){
        color1=1,color2=1;
        while(color[u[i]][color1])++color1;
        while(color[v[i]][color2])++color2;
        //寻找到mex(C1),mex(C2)
        color[u[i]][color1]=v[i];
        color[v[i]][color2]=u[i];
        //标记
        if(color1==color2)continue;
        //若颜色不冲突，则直接染色
        for(int tmp=color2,w=v[i];w;w=color[w][tmp],tmp^=color1^color2){
            swap(color[w][color1],color[w][color2]);
        }
        //通过异或实现color1和color2的交替染色
    }
    print(ans),puts("");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=ans;++j){
            if(color[u[i]][j]==v[i]){
                print(j),printf(" ");
            }
        }
    }
    //匹配输出
    return 0;
}

如果你觉得这篇题解讲得还算好的话，可以点个赞支持一下呀，谢谢大家！