题解：P14900 [ICPC 2018 Yokohama R] Four-Coloring

· · 题解

太困难了，zfr 做了好久都不会，由此钦定这个题是上位黑题。

首先发现对于一个 \deg\le 3 的节点，我直接删掉是不影响后面的染色的，因为别的节点最多占掉三个颜色，我染剩下的颜色即可。

不难发现无论我们怎么删，整张图必然存在一个度数 \le 4 的节点。 ::::info[证明] 考虑图形的边界，一个五度点对应边界的角度一定 \ge 180^{\circ}，假如全部是五度点，那么整个图形必然不能闭合。

证毕。 ::::

考虑怎么处理四度点。我们记四个颜色分别是 1,2,3,4，如果一个四度点 v 相邻的点没有占据所有颜色，那我们依旧可以随便取一个没被占据的颜色。

如果 v 周围四个点的颜色恰好是 1,2,3,4，那我们进行如下操作：

  1. 钦定一个颜色 c，选择一个相邻节点 u，满足 u 的颜色 c'\ne c。
  2. 把所有与 u 相邻的颜色为 c 的节点染成 c'。
  3. 递归下去，直到所有节点的颜色都不与相邻节点相同。
  4. 如果此时与 v 相邻的节点颜色还是 1,2,3,4，那么重新选择一个 c,u，否则直接染一个没被占据的颜色

然后这个东西看上去没什么正确性，我们给一个证明。 ::::info[证明] 考虑加入我选择节点 u，颜色 c，与 v 相邻的节点的颜色是 c 的节点是 u_0，那么我们进行操作之后，如果 u 和 u_0 互换颜色，那么就倒闭了。

考虑互换颜色实际上等于存在一条路径 u,x_1,x_2\dots x_{l},u_0，满足这个路径上面第奇数个点的颜色是 u 的颜色，第偶数个点的颜色是 c。

如果我每次操作都会进行一次颜色的互换，那么等价于对于与 u 相连的四个点都存在一条相连的路径。

考虑两条路径，如果没有公共的起点 / 终点，那么路径上的颜色不一样，必定不交。

假如存在这样的路径，那么我们对于 v 和与 v 相邻的四个节点，两两之间存在一条不交的路径（这里其实需要补充一下，有公共起点 / 终点的是可以相交的，但是不影响），于是存在 K_5 子图，与原图是平面图矛盾。 :::: 然后直接做就可以了，时间复杂度 O(n^2)。

这个题有一个很聪明的做法，我们按照 (x,y) 的二元组对所有点排序，按照顺序填颜色即可，这样可以少写一个 priority_queue。

const int N=1e4+5,inf=1e9+7;
int n,m,T;
vector<int> to[N];
int id[N];
void add(int a,int b){to[a].pb(b),to[b].pb(a);}
bool vis[N];
int col[N],x[N],y[N]; 
bool cmp(int a,int b){
    if(x[a]==x[b])return y[a]<y[b];
    return x[a]<x[b];
}
bool cnt[5];
void modify(int u,int x,int y){
    col[u]=x;
    for(int v:to[u])if(vis[v])if(col[v]==x)modify(v,y,x);
}
int getc(int u){
    memset(cnt,0,sizeof cnt);
    for(int v:to[u])if(vis[v])cnt[col[v]]=1;
    for(int i=1;i<=4;i++)if(!cnt[i])return i;
    return 0;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        x[i]=read(),y[i]=read();
    for(int i=1;i<=n;i++)   
        id[i]=i;
    for(int i=1;i<=m;i++)
        add(read(),read());
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++){
        int u=id[i]; 
        col[u]=getc(u);
        if(!col[u])for(int v:to[u])if(vis[v]){
            for(int c=1;c<=4;c++)if(c!=col[v]){
                modify(v,c,col[v]);
                col[u]=getc(u);
                if(col[u])break;
            }
            if(col[u])break;
        }
        vis[u]=1;
    }
    for(int i=1;i<=n;i++)printf("%d\n",col[i]);
    return 0;
}
//  Think twice,code once