[CodeForces-1198E] Rectangle Painting 2

题解：

朴素做法，是最小点覆盖点数是n*n，考虑离散化后，把每个矩形块看作点，跑最小点权覆盖。

将矩形：左下角（x1,y1）到右上角 (x2,y2) 的 x2++,y2++,那么这样离散化后每个x1<=x<x2,y1<=y<y2，

（x,y）都能表示为一个左下闭区间，右上开的一个矩形，且这些矩形刚好不多不少的覆盖完了题目所形成的区域。

且每个矩形能被x或y覆盖，连INF边即可，跑最小点权覆盖。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510,M = 1e5 + 10;
const LL INF = 1e15;
int h[N],e[M],ne[M],idx;
LL f[M];
struct Node{
    int x1,y1,x2,y2;
}t[N];
typedef pair<int,int> P;
set<P> st;
void add(int a,int b,LL c){
    if(st.count({a,b}))return ;
    st.insert({a,b});
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
int n,m;
int S,T;
vector<int> vx,vy;
int get(int x,int flg){
    if(!flg){
        return lower_bound(vx.begin(),vx.end(),x)-vx.begin();
    }
    else{
        return lower_bound(vy.begin(),vy.end(),x)-vy.begin();
    }
}
int d[N],cur[N],q[N];
bool bfs(){
    memset(d,-1,sizeof d);
    int hh = 0,tt = 0;
    q[0] = S,cur[S] = h[S],d[S] = 0;
    while(hh<=tt){
        int u = q[hh++];
        for(int i = h[u];~i;i=ne[i]){
            int j = e[i];
            if(d[j] == -1 && f[i]){
                d[j] = d[u] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if(j == T)return true;
            }
        }
    }
    return false;
}
LL find(int u,LL limit){
    if(u == T)return limit;
    LL flow = 0;
    for(int i = cur[u];~i&&flow<limit;i=ne[i]){
        int j = e[i];
        cur[u] = i;
        if(d[j] == d[u] + 1 && f[i]){
            LL t = find(j,min(limit-flow,f[i]));
            if(!t)d[j] = -1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
LL dinic(){
    LL res = 0,flow;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
int main(){
    // freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    S = N - 2,T = N - 1;
    for(int i = 1;i<=m;++i){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x2++,y2++;
        t[i] = {x1,y1,x2,y2};
        vx.push_back(x1);
        vx.push_back(x2);
        vy.push_back(y1);
        vy.push_back(y2);
    }
    
    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    int rl = vx.size();
   
    for(int i = 1;i<=m;++i){
        // cout<<i<<'\n';
        int x1 = get(t[i].x1,0);
        int x2 = get(t[i].x2,0);
        int y1 = get(t[i].y1,1);
        int y2 = get(t[i].y2,1);
        for(int x = x1;x<x2;++x){
            for(int y = y1;y<y2;++y){
                add(x,y+rl,INF);
            }
        }
    }
    // puts("!!!");
    // cout<<vx.size()<<'\n';
    for(int i = 0;i<(int)vx.size()-1;++i){
        add(S,i,vx[i+1]-vx[i]);
    }
    // puts("!!!");
    for(int i = 0;i<(int)vy.size()-1;++i){
        add(i+rl,T,vy[i+1]-vy[i]);
    }
    
    LL d = dinic();
    printf("%lld\n",d);
    return 0;
}