CF1198E Rectangle Painting 2

网络流好题，模型是二分图的最小覆盖

题解：

首先要想到一个很显然的贪心，对于一个黑格，他要么是在纵向上被完全覆盖，要么是在横向上被完全覆盖，其中“完全覆盖”是指整行或整列都被一次性涂白

稍微思考一下，题目变成了在纵向上选一些列，在横向上选一些行，使得将他们完全覆盖后不存在一个黑格，问最少的选择数

我们可以将有黑格的行看成一个点集，将有黑格的列看成另一个点集，对于两者之间的交点，看成两个点集之间的连边，于是我们就得到了一个二分图

题目变成了二分图的最小覆盖问题

由于这张二分图的点数很和边数多，我们考虑离散与压缩，并用网络流进行优化，因为有一个重要定理：最小覆盖=最大流

离散后，对于一个矩形，我们只考虑它的四个边界，两个对立边界中所有点的代价全部赋给靠右（或下）的边界点，即（右减左，或下减上）

我们知道，网络流中点的代价是由超源和超汇给他的，于是从超源向行点连边，容量为其代价，从列点向超汇连边，容量为其代价，行点和列点之间的连边即两者是否相交，容量为无穷大

具体的，在代码实现中，我们将一条边界形如$[l,r]$的左闭右闭区间，修改成形如$[l,r+1)$的左闭右开区间

这是一个十分套路的方便操作，我们可以清楚的判定一个点到底是要被算进左边的代价还是右边的代价，并防止最右边被漏掉，详细可以看代码

代码轻微复杂，特先做出注释：

.x.x=x1

.x.y=y1

.y.x=x2

.y.y=y2

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define pii pair<int,int>
#define x first
#define y second

const int oo=0x7fffffff,N=405,M=N*N+5;
int en=1,h[N],n,m,s,t,cur[N],d[N],ux[N],uy[N],uxn,uyn;

pair<pii,pii> a[N]; //pii套pii~

struct edge{
    int n,v,w;
}e[M<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

bool bfs(int s,int t){
    for(int i=s;i<=t;i++) d[i]=0,cur[i]=h[i];
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(!d[y]&&e[i].w){
                d[y]=d[x]+1;
                if(y==t) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int flow,int t){
    if(x==t) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].w){
            int tp=dfs(y,min(rest,e[i].w),t);
            rest-=tp;
            e[i].w-=tp;
            e[i^1].w+=tp;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(a[i].x.x);
        read(a[i].x.y);
        read(a[i].y.x);a[i].y.x++; //改成左闭右开区间
        read(a[i].y.y);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]=uy[++uyn]=n+1; //加一个边界，以防遗漏最右点
    sort(ux+1,ux+1+uxn);
    sort(uy+1,uy+1+uyn);
    uxn=unique(ux+1,ux+1+uxn)-ux-1; //离散
    uyn=unique(uy+1,uy+1+uyn)-uy-1;
    s=0,t=uxn+uyn+1; //超源超汇
    for(int i=1;i<=m;i++){
        a[i].x.x=lower_bound(ux+1,ux+1+uxn,a[i].x.x)-ux; //离散后的坐标
        a[i].x.y=lower_bound(uy+1,uy+1+uyn,a[i].x.y)-uy;
        a[i].y.x=lower_bound(ux+1,ux+1+uxn,a[i].y.x)-ux;
        a[i].y.y=lower_bound(uy+1,uy+1+uyn,a[i].y.y)-uy;
        for(int x=a[i].x.x;x<a[i].y.x;x++)
            for(int y=a[i].x.y;y<a[i].y.y;y++)
                add(x,y+uxn,oo),add(y+uxn,x,0); //添加交点的无穷边
    }
    for(int i=1;i<uxn;i++) add(s,i,ux[i+1]-ux[i]),add(i,s,0); //根据相邻边之间的距离，计算它的代价，并从超源向行点连边
    for(int i=1;i<uyn;i++) add(i+uxn,t,uy[i+1]-uy[i]),add(t,i+uxn,0);
    write(dinic(s,t)); //最大流=最小覆盖
}