CF传送门
洛谷传送门
解题思路
显然有一条性质：每次选择一定选择一整行和一整列。
考虑暴力做法：
把每个点的横坐标连向纵坐标，边权为1，跑一遍最小点覆盖，求出最少选择多少行数+列数使其覆盖所有的边。
由于点可能很多，但是矩形可能很少，所以我们考虑优化。
把所有横纵坐标分别扔到一个数组中，离散化处理。
枚举每一个离散化后的横坐标（存储在zx数组中），则由源点s点连向每一个横坐标 i ，权值为 zx[i]-zx[i-1] 。纵坐标同理。
然后枚举每一个离散化后的矩形，若其全部需要覆盖，则由这个矩形的右下角的横坐标连向纵坐标，权值为inf。
建完图后，跑一遍带权的最小点覆盖（最大流）即可。
AC代码
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<iomanip> 5 #include<cmath> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 const int maxn=10005; 10 const int inf=0x3f3f3f3f; 11 int n,m,cnt=-1,p[maxn],dep[maxn],cur[maxn],s,t,zx[maxn],zy[maxn],cntx,cnty; 12 struct kkk{ 13 int lx,ly,rx,ry; 14 }a[maxn]; 15 struct node{ 16 int v,next,cap,flow; 17 }e[maxn*10]; 18 void add(int u,int v,int cap,int flow){ 19 cnt++; 20 e[cnt].v=v; 21 e[cnt].next=p[u]; 22 e[cnt].cap=cap; 23 e[cnt].flow=flow; 24 p[u]=cnt; 25 } 26 bool bfs(){ 27 queue<int> q; 28 memset(dep,-1,sizeof(dep)); 29 q.push(s); 30 dep[s]=0; 31 while(!q.empty()){ 32 int u=q.front(); 33 q.pop(); 34 for(int i=p[u];i!=-1;i=e[i].next){ 35 if(e[i].cap-e[i].flow>0&&dep[e[i].v]==-1){ 36 dep[e[i].v]=dep[u]+1; 37 q.push(e[i].v); 38 } 39 } 40 } 41 if(dep[t]==-1) return false; 42 return true; 43 } 44 int dfs(int u,int maxflow){ 45 if(u==t||maxflow==0) return maxflow; 46 int flow=0; 47 for(int &i=cur[u];i!=-1;i=e[i].next){ 48 if(dep[e[i].v]==dep[u]+1&&e[i].cap>e[i].flow){ 49 int fl=dfs(e[i].v,min(maxflow,e[i].cap-e[i].flow)); 50 maxflow-=fl; 51 flow+=fl; 52 e[i].flow+=fl; 53 e[i^1].flow-=fl; 54 if(maxflow==0) break; 55 } 56 } 57 return flow; 58 } 59 int dinic(){ 60 int ans=0; 61 while(bfs()){ 62 for(int i=s;i<=t;i++){ 63 cur[i]=p[i]; 64 } 65 ans+=dfs(s,inf); 66 } 67 return ans; 68 } 69 int main(){ 70 memset(p,-1,sizeof(p)); 71 int n,m; 72 cin>>n>>m; 73 s=0,t=201; 74 for(int i=1;i<=m;i++){ 75 scanf("%d%d%d%d",&a[i].lx,&a[i].ly,&a[i].rx,&a[i].ry); 76 a[i].lx--; 77 a[i].ly--; 78 zx[++cntx]=a[i].lx; 79 zx[++cntx]=a[i].rx; 80 zy[++cnty]=a[i].ly; 81 zy[++cnty]=a[i].ry; 82 } 83 sort(zx+1,zx+cntx+1); 84 sort(zy+1,zy+cnty+1); 85 cntx=unique(zx+1,zx+cntx+1)-zx-1; 86 cnty=unique(zy+1,zy+cnty+1)-zy-1; 87 for(int i=2;i<=cntx;i++){ 88 for(int j=2;j<=cnty;j++){ 89 for(int k=1;k<=m;k++){ 90 if(a[k].lx<=zx[i-1]&&a[k].rx>=zx[i]&&a[k].ly<=zy[j-1]&&a[k].ry>=zy[j]){ 91 add(i,j+100,inf,0); 92 add(j+100,i,0,0); 93 break; 94 } 95 } 96 } 97 } 98 for(int i=2;i<=cntx;i++) add(s,i,zx[i]-zx[i-1],0),add(i,s,0,0); 99 for(int i=2;i<=cnty;i++) add(i+100,t,zy[i]-zy[i-1],0),add(t,i+100,0,0); 100 cout<<dinic(); 101 return 0; 102 }