CF1198E Rectangle Painting 2

网络流$+$二分图最小覆盖。

把一个$h*w$的矩形区域覆盖的代价是$\min(h,w)$，因此选择一个大小为$1*k$或$k*1$的区间显然非常优秀。如果多个区间可以合并的话，$n*k$显然代价等于$n* \min(1,k)$或$k* \min(n,1)$，并且数据中区间所占行数和列数离散化后又不是很多，因此可以这么做！

关于离散化

• $uxn，uyn$保存的是离散化后数组总个数，不是最大值
• 通过画图可以发现，$ux[i+1]-ux[i]$确实包含了所有的矩形，但是有可能把把两个矩形切成三个矩形
• 然然后为什么要变作闭右开区间呢，因为这样确实可以很好的覆盖所有的数，自己模拟吧（），但这真的是个技巧欸

我居然看懂了！/fad

关于数据范围
首先这个500就很玄学啊（我死都不会说我看了题解开的
链式前向星的$e$数组开$maxn*maxn$就好了，毕竟是二维平面转一维。

关于最小覆盖
在这个题目中，最小覆盖=最小割=最大流。

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000000000
#define RP pair<long long,long long>
#define maxn 500
#define x first
#define y second
using namespace std;
ll n,m;
ll ux[maxn<<2],uy[maxn<<2];
ll uxn,uyn;
ll s,t,ans;
ll d[maxn],l,r,q[maxn];
ll cnt=1,hd[maxn];
pair<RP,RP> a[maxn];
struct Node{
    ll nx,to,dis;
}e[maxn*maxn*4];

inline ll read(){
    ll xx=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        xx=(xx<<1)+(xx<<3)+(c^48),c=getchar();
    return f?-xx:xx;
}

inline ll mn(ll u,ll v){
    return u<v?u:v;
}

inline void add(ll u,ll v,ll w){
    e[++cnt].to=v;
    e[cnt].nx=hd[u];
    e[cnt].dis=w;
    hd[u]=cnt;
}

inline ll bfs(){
    memset(d,0,sizeof(d));
    d[s]=1;
    q[l=r=1]=s;
    while(l<=r){
        ll u=q[l++];
        for(register int i=hd[u];i;i=e[i].nx){
            ll to=e[i].to;
            if(e[i].dis&&!d[to])
                q[++r]=to,d[to]=d[u]+1;
        }
    }
    return d[t];
}

inline ll dfs(ll u,ll limit){
    if(u==t)      return limit;
    ll flow=0;
    for(register int i=hd[u];i&&limit;i=e[i].nx){
        ll to=e[i].to;
        if(d[to]==d[u]+1&&e[i].dis){
            ll fj=dfs(to,mn(limit,e[i].dis));
            e[i].dis-=fj;
            e[i^1].dis+=fj;
            flow+=fj;
            limit-=fj;
        }
    }
    if(!flow)    d[u]=0;
    return flow;
}

int main(){
    n=read();m=read();
    for(register int i=1;i<=m;++i){
        a[i].x.x=read();
        a[i].x.y=read();
        a[i].y.x=read();
        a[i].y.y=read();
        ++a[i].y.x;
        ++a[i].y.y;
        ux[++uxn]=a[i].x.x;
        uy[++uyn]=a[i].x.y;
        ux[++uxn]=a[i].y.x;
        uy[++uyn]=a[i].y.y;
    }
    ux[++uxn]=n+1,
    uy[++uyn]=n+1;
    sort(ux+1,ux+uxn+1);
    sort(uy+1,uy+uyn+1);
    uxn=unique(ux+1,ux+uxn+1)-ux-1;
    uyn=unique(uy+1,uy+uyn+1)-uy-1;
    s=0,t=uxn+uyn+1;
    for(register int i=1;i<=m;++i){
        a[i].x.x=lower_bound(ux+1,ux+uxn+1,a[i].x.x)-ux;
        a[i].x.y=lower_bound(uy+1,uy+uyn+1,a[i].x.y)-uy;
        a[i].y.x=lower_bound(ux+1,ux+uxn+1,a[i].y.x)-ux;
        a[i].y.y=lower_bound(uy+1,uy+uyn+1,a[i].y.y)-uy;
        for(register int j=a[i].x.x;j<a[i].y.x;++j)
            for(register int k=a[i].x.y;k<a[i].y.y;++k)
                add(j,k+uxn,INF),add(k+uxn,j,0);
    }
    for(register int i=1;i<uxn;++i)    add(s,i,ux[i+1]-ux[i]),add(i,s,0);
    for(register int i=1;i<uyn;++i)    add(i+uxn,t,uy[i+1]-uy[i]),add(t,i+uxn,0);
    while(bfs())
        ans+=dfs(s,INF);
    printf("%lld\n",ans);
    return 0;
}