对于该题的建模
考虑类型为二分图,即对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; }