题解归档 - cf1198E

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

• 本地编号：cf1198E
• 本地来源：problems/cf1198E/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/E
• 原始标题：1198E — Rectangle Painting 2

思路

1198E — Rectangle Painting 2

题意

$n\times n$ 网格（$n\le 10^9$），黑格为至多 $m\le 50$ 个矩形的并。一次可选子矩形全部染白，代价为 $\min(h,w)$。求最小总代价。

关键转化

每个黑格 $(x,y)$ 最终必被某次「扫行」或「扫列」型矩形覆盖（等价于选一条过该点的水平/竖直带）。代价 $\min(h,w)$ 使得：

• 选一条 竖直带（覆盖某 $x$ 方向区间）代价 = 区间在 $x$ 上的长度；
• 选一条 水平带（覆盖某 $y$ 方向区间）代价 = 区间在 $y$ 上的长度。

于是为 带权二分图最小点覆盖 = Dinic 最大流（最小割）。

坐标压缩

收集所有矩形的 $x_1,\,x_2+1,\,y_1,\,y_2+1$，去重得断点 $a[1..A],\,b[1..B]$。压缩格点 $(i,j)$（$1\le i<A,\,1\le j<B$）表示原图中矩形 $[a_i,a_{i+1})\times[b_j,b_{j+1})$；若与任一黑矩形相交则标黑。

建图

• 源 $S=0$，汇 $T=A+B+1$。
• $x$ 区间节点 $i$：$S\to i$，容量 $a_{i+1}-a_i$。
• $y$ 区间节点 $A+j$：$A+j\to T$，容量 $b_{j+1}-b_j$。
• 黑格 $(i,j)$：$i\to A+j$，容量 $\infty$。

最大流 = 最小染白代价。$m=0$ 直接输出 $0$。

Catalog 备注

catalog_priority.json 标为「二维 BIT」，实际主流解法是坐标压缩 + 最小割（与 1198D 的区间 DP / $\max$ 代价对称）。lib/数据结构(二维树状数组).cpp 已存在，本题不新增 BIT 模板；Dinic 见 lib/图论(Dinic最大流).cpp（本题手写标准 Dinic）。

验证

• 样例 1 → 4，样例 2 → 3
• stress.py -n 200（$n\le 12$ 小图区间 DP brute.cpp 对拍，代价用 $\min$）

代码

来源：problems/cf1198E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:00:29
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=305,INF=1e18;
struct edge{ll to,cap,rev;};
vector<edge>g[maxn];
ll n,m,i,j,k,u,v,ss,tt,tot,flow;
ll a[maxn],b[maxn],xa[maxn],ya[maxn],xb[maxn],yb[maxn],vis[maxn][maxn];
ll level[maxn],cur[maxn];
void add(ll x,ll y,ll cap){
    g[x].push_back({y,cap,(ll)g[y].size()});
    g[y].push_back({x,0,(ll)g[x].size()-1});
}
bool bfs(){
    ll i,h=0,tl=1,q[maxn+5];
    for(i=0;i<=tot;i++) level[i]=-1,cur[i]=0;
    level[ss]=0,q[0]=ss;
    while(h<tl){
        u=q[h++];
        for(i=0;i<(ll)g[u].size();i++){
            edge e=g[u][i];
            if(e.cap>0 and level[e.to]==-1){
                level[e.to]=level[u]+1;
                q[tl++]=e.to;
            }
        }
    }
    return level[tt]!=-1;
}
ll dfs(ll u,ll aug){
    ll i,v,fl=0;
    if(u==tt) return aug;
    for(i=cur[u];i<(ll)g[u].size();i++){
        cur[u]=i;
        edge e=g[u][i];
        if(e.cap>0 and level[e.to]==level[u]+1){
            v=dfs(e.to,min(aug,e.cap));
            if(v>0){
                g[u][i].cap-=v;
                g[e.to][e.rev].cap+=v;
                fl+=v;
                aug-=v;
                if(aug==0) break;
            }
        }
    }
    return fl;
}
ll dinic(){
    ll ans=0,aug;
    while(bfs()){
        while((aug=dfs(ss,INF))>0) ans+=aug;
    }
    return ans;
}
ll lb(ll *zc,ll sl,ll z){
    ll l=1,r=sl,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(zc[mid]<z) l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main(){
    cin>>n>>m;
    if(m==0){
        cout<<"0\n";
        return 0;
    }
    a[0]=0,b[0]=0;
    a[++a[0]]=1;a[++a[0]]=n+1;
    b[++b[0]]=1;b[++b[0]]=n+1;
    for(i=1;i<=m;i++){
        cin>>xa[i]>>ya[i]>>xb[i]>>yb[i];
        a[++a[0]]=xa[i];
        a[++a[0]]=xb[i]+1;
        b[++b[0]]=ya[i];
        b[++b[0]]=yb[i]+1;
    }
    sort(a+1,a+a[0]+1);
    k=1;
    for(i=2;i<=a[0];i++) if(a[i]!=a[k]) a[++k]=a[i];
    a[0]=k;
    sort(b+1,b+b[0]+1);
    k=1;
    for(i=2;i<=b[0];i++) if(b[i]!=b[k]) b[++k]=b[i];
    b[0]=k;
    memset(vis,0,sizeof(vis));
    for(i=1;i<=m;i++){
        for(u=lb(a,a[0],xa[i]);u<=lb(a,a[0],xb[i]+1)-1;u++)
            for(j=lb(b,b[0],ya[i]);j<=lb(b,b[0],yb[i]+1)-1;j++)
                vis[u][j]=1;
    }
    ss=0;
    tt=a[0]+b[0]+1;
    tot=tt;
    for(i=0;i<=tot;i++) g[i].clear();
    for(i=1;i<a[0];i++) add(ss,i,a[i+1]-a[i]);
    for(i=1;i<b[0];i++) add(a[0]+i,tt,b[i+1]-b[i]);
    for(i=1;i<a[0];i++) for(j=1;j<b[0];j++) if(vis[i][j]) add(i,a[0]+j,INF);
    cout<<dinic()<<"\n";
    return 0;
}