P7307题解

· · 题解

Part 1：前言

神仙构造题。

下文中，我们用小写代替原文中的大写，用 col_i 代表原文的 c_i。

Part 2：正文

首先可以猜测到最小的颜色数为度数最大的点的度数，不会证也没关系，有一点是显然的，就是最终答案 c 不小于度数最大的点的度数 d_max。

注意到题目给了一个非常奇怪的范围：x 为不小于 c 的最小的 2 的正整数次幂。换言之，x=2^{\left\lceil{\log_2 c}\right\rceil}\ge2^{\left\lceil{\log_2 d_{max}}\right\rceil}，对于这种范围，一般可以想到是分治构造了。

考虑对边集进行划分，每次我们都试图将原来的边集划分为两个边集，每个边集中度数最大的点都是原来边集中最大的点的度数的一半。当我们把边集划分后点的度数最大是 1 时，就把这个边集内所有的边染成同色的。这样做最多会分治 \left\lceil{\log_2 d_{max}}\right\rceil 轮，每轮合并答案都会让颜色种类数乘 2，答案不会超过 2^{\left\lceil{\log_2 d_{max}}\right\rceil}。

接下来考虑如何划分。我们新建两个虚点 x',y' 分属于二分图两侧。把一侧度数为奇数的点向另一侧的虚点连边，这样每个点的度数都是偶数，一定存在一条欧拉回路。我们将欧拉回路上的边交替染色，同色的边属于一个边集，这样就能使得每个点点度数大小减半（感性理解，对于每个点，出现在欧拉回路中度数除二上取整次，每次涉及到两条边且被染成不同颜色）。

时间复杂度 O(n\log n)（这里视 n,m 同阶）。

Part 3：代码

#define u first
#define v second
#define pb push_back
const int N=2e5+7,M=1e6+7;
int l,r,m,n;
vector<np>e,ne;
vector<int>to[N];
int tim[N],deg[N],_clock=0;
int col[M];
int vis[M];

void reset(int x,vector<int>&V){
    tim[x]=_clock;
    to[x].clear();
    deg[x]=0;V.pb(x);
}

int c=0;

void dfs(int u){
    for(;!to[u].empty();){
        int id=to[u].back();
        to[u].pop_back();
        if(vis[id]==_clock)continue;

        col[id]=(c^=1);
        vis[id]=_clock;
        dfs(ne[id].u+ne[id].v-u);
    }
}

vector<int>solve(vector<np>E){
    if(!E.size())return {};
    ++_clock;
    ne=E;
    vector<int>V;
    bool flag=0;
    int siz=E.size(),nsiz=ne.size();
    for(int i=0;i<siz;i++){
        np edge=E[i];
        int u=edge.u,v=edge.v;
        if(tim[u]!=_clock)reset(u,V);
        if(tim[v]!=_clock)reset(v,V);
        deg[u]++,deg[v]++;
        if(deg[u]>1||deg[v]>1)flag=1;
        to[u].pb(i),to[v].pb(i);
    }
    if(!flag){
        vector<int>res(E.size(),1);
        return res;
    }
    deg[n+1]=0;
    for(int i:V){
        if(deg[i]&1){
            if(i<=l||i==n+1){
                deg[n+2]++,deg[i]++;
                to[n+2].pb(nsiz),to[i].pb(nsiz),ne.pb({i,n+2});
                nsiz++;
            }else{
                deg[n+1]++,deg[i]++;
                to[n+1].pb(nsiz),to[i].pb(nsiz),ne.pb({i,n+1});
                nsiz++;
            }
        }
    }
    if(deg[n+1]&1){
        deg[n+2]++,deg[n+1]++;
        to[n+2].pb(nsiz),to[n+1].pb(nsiz),ne.pb({n+1,n+2});
        nsiz++;
    }
    for(int i:V){dfs(i);}
    vector<np>el,er;
    vector<int>cl;
    for(int i=0;i<siz;i++){
        if(col[i])er.pb(E[i]);
        else el.pb(E[i]);
        cl.pb(col[i]);
    }
    vector<int>rl=solve(el);
    vector<int>rr=solve(er);
    int ansl=0;
    for(int i:rl)ansl=max(ansl,i);
    vector<int>res;
    int tmpl=0,tmpr=0;
    for(int i=0;i<siz;i++){
        if(cl[i])res.pb(ansl+rr[tmpr++]);
        else res.pb(rl[tmpl++]);
    }
    return res;
}

int main(){
    l=read(),r=read(),m=read();n=l+r;
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        e.pb(mp(u,v+l)); 
    }
    vector<int>ans=solve(e);
    int res=0;
    for(int i:ans)res=max(res,i);
    cout<<res<<endl;
    for(int i:ans)printf("%d\n",i);
    return 0;
}