[eJOI2019] 矩形染色 Solution

· · 题解

wssb，感谢 zhy 指教。

提供一个简单得多的做法：每个格子只会被两条来自不同方向的对角线覆盖，考虑把每个格子看成一条边，问题转换成了二分图最小权点覆盖问题。这是经典网络流问题，最小割建模可以拿到 40 分。

观察一下连边的形式，我们对于格子 (i,j) 定义 x=i+m-j,y=i+j-1，那么这个格子会对左部的 x 与右部的 y 连边。

推推式子，可以得到 (x,y) 有连边当且仅当：

y\in [m+1-x,2n+m-1-x]\cap [1-m+x,x+m-1]

且要求 x+y+m 是奇数。

将原图按照奇偶分类后就变成了如下问题：对于每一个左部点，向右部点的一个区间连边，求最大流。

这个问题十分经典，我们考虑直接贪心：按照右端点排序，每次选择最靠近左端点的流。这个可以用并查集维护。

按照右端点排序可以用计数排序做到 O(n)，所以总时间复杂度可以做到 O(n\alpha(n))。

这里是 O(n\log n) 直接 sort 的代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){/*...*/}
typedef long long ll;
const int N=400003;
int n,m,rk,tp;
int a[N],b[N];
int val[N];
struct seq{
    int l,r,x;
    friend bool operator<(const seq a,const seq b){
        return a.r<b.r;
    }
}s[N];
int f[N];
int rt(int x){
    if(f[x]==x) return x;
    return f[x]=rt(f[x]);
}
ll solve(){
    for(int i=1;i<=rk+1;++i) f[i]=i;
    sort(s+1,s+tp+1);
    ll sum=0;
    for(int i=1;i<=tp;++i){
        while(rt(s[i].l)<=s[i].r&&s[i].x){
            int p=rt(s[i].l);
            int t=min(val[p],s[i].x);
            s[i].x-=t;val[p]-=t;
            sum+=t;
            if(!val[p]) f[p]=p+1;
        }
    }
    return sum;
}
int main(){
    n=read();m=read();
    for(int i=1;i<n+m;++i) a[i]=read();
    for(int i=1;i<n+m;++i) b[i]=read();
    ll res=0;
    for(int p=1,t=m&1;;p^=1,t^=1){
        tp=rk=0;
        for(int i=p?1:2;i<n+m;i+=2){
            int l=max(m+1-i,1-m+i);
            int r=min(n+n+m-1-i,i+m-1);
            if((l&1)!=t) ++l;
            if((r&1)!=t) --r;
            l=(l+1)>>1;
            r=(r+1)>>1;
            if(l<=r){++tp;s[tp].l=l;s[tp].r=r;s[tp].x=a[i];}
        }
        for(int i=t?1:2;i<n+m;i+=2) val[++rk]=b[i];
        res+=solve();
        if(!p) break;
    }
    printf("%lld\n",res);
    return 0;
}