ABC205F

对于该题的建模
考虑类型为二分图，即对N个点进行拆点，左边与行相连，容量为1，右边与列相连，容量为1，然后跑最大流即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e6+10;
struct Edge{
    int v,next,w;
}edge[N<<1];
int tot=1,head[N],S,T;
const int INF = 1e9;
int d[N],cur[N];
void add(int u,int v,int w1,int w2){
    edge[++tot]={v,head[u],w1};
    head[u]=tot;
    edge[++tot]={u,head[v],w2};
    head[v]=tot;
}
bool bfs(){
    queue<int>q;
    memset(d,0,sizeof d);
    d[S]=1;cur[S]=head[S];
    q.push(S);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            int w=edge[i].w;
            if(w&&!d[v]){
                cur[v]=head[v];
                d[v]=d[u]+1;
                if(v==T)return 1;
                q.push(v);
            }

        }
    }
    return 0;
}
int dfs(int u,int limit){
    if(u==T)return limit;
    int flow=0,k;
    for(int i=cur[u];i&&flow<limit;i=edge[i].next){
        cur[u]=i;
        int v=edge[i].v;
        int w=edge[i].w;
        if(w&&d[v]==d[u]+1){
            k=dfs(v,min(w,limit-flow));
            if(!k)d[v]=0;
            edge[i].w-=k;
            edge[i^1].w+=k;
            flow+=k;
        }

    }
    return flow;
}



int dinic(){
    int maxflow=0,flow;
    while(bfs())while(flow=dfs(S,INF))maxflow+=flow;
    return maxflow;
}


int id[210][210];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    S=2e5;
    T=S+1;
    for(int i=1;i<=n;i++){
        add(S,i,1,0);
    }
    for(int i=1;i<=m;i++){
        add(i+n,T,1,0);
    }
    for(int i=1;i<=k;i++){
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int u=i+n+m;
        int v=i+n+m+2*k;
        for(int j=x1;j<=x2;j++){
            add(j,u,1,0);
        }
        add(u,v,1,0);
        for(int j=y1;j<=y2;j++){
            add(v,j+n,1,0);
        }
    }
    cout<<dinic();
    return 0;
}