「CodeForces 1198E」 Rectangle Painting 2

There is a square grid of size 𝑛×𝑛. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min(ℎ,𝑤) to color a rectangle of size ℎ×𝑤. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of 𝑚 rectangles.

大致题意 📖

有一个 $n \times n (n <= 1e9)$ 的矩阵，其中有 $m (m <= 50)$ 个黑块，其余为白块，你可以选择一个 $n \times m$ 矩阵，将其染成白色，费用为 $min(n,m)$ ，求将涂染成全白的最小费用

链接 🔗

「CodeForces 1198E」 Rectangle Painting 2

题解 ❓

$1198D$ 的升级版，不过是两个问题
相较上个问题, $max$ -> $min$ ,因此可以知道，只选[1,m]或[n,1]是最优的,因为费用都为 $1$
因此就是选最少的行和列，覆盖所有黑格子。于是题目就转化为网络流问题了

代码

struct
{
    ll x,y,r,c;
}a[maxd];
ll fx[maxd],fy[maxd],tot,sx,sy;
int main()
{
//    __IN;__OUT;
    ll n,m; RLL(m);RLL(n); init();
    F(n)
    {
        RLL(fx[sx]);a[i].x = fx[sx++];
        RLL(fy[sy]);a[i].y = fy[sy++];
        RLL(fx[sx]);a[i].r = ++fx[sx++];
        RLL(fy[sy]);a[i].c = ++fy[sy++];
    }
    sort(fx,fx+sx);sort(fy,fy+sy);
    sx =  unique(fx,fx+sx) - fx;
    sy =  unique(fy,fy+sy) - fy;
    s = 0, t = sx+sy+1;
    FOR(i,1,sx-1) addedge(s,i,fx[i] - fx[i-1]);
    FOR(i,1,sy-1) addedge(sx - 1 + i,t,fy[i] - fy[i-1]);
    F(n)
    {
        a[i].x = lower_bound(fx, fx + sx, a[i].x) - fx;
        a[i].y = lower_bound(fy, fy + sy, a[i].y) - fy;
        a[i].r = lower_bound(fx, fx + sx, a[i].r) - fx;
        a[i].c = lower_bound(fy, fy + sy, a[i].c) - fy;
        for (int x = a[i].x; x < a[i].r; x++)
            for (int y = a[i].y; y < a[i].c; y++)  addedge(x + 1, sx + y, 2e9);
    }
    PLN(maxflow());
 
    return 0;
}

dinnerhunt