传送门
洛谷 https://www.luogu.org/problemnew/show/P1402
Solution
大致思想同这个 -- 洛谷 1231 https://www.cnblogs.com/mle-world/p/10549680.html
代码实现
- #include<bits/stdc++.h>
- using namespace std;
- const int N=500010,Inf=1e9+10;
- int front[N],cnt,s,t,n;
- struct node
- {
- int to,nxt,w;
- }e[1500010];
- queue<int>Q;
- int dep[N];
- void Add(int u,int v,int w)
- {
- e[cnt]=(node){v,front[u],w};front[u]=cnt++;
- e[cnt]=(node){u,front[v],0};front[v]=cnt++;
- }
- bool bfs()
- {
- memset(dep,0,sizeof(dep));
- Q.push(s);dep[s]=1;
- while(!Q.empty())
- {
- int u=Q.front();Q.pop();
- for(int i=front[u];i!=-1;i=e[i].nxt)
- {
- int v=e[i].to;
- if(!dep[v] && e[i].w)
- {
- dep[v]=dep[u]+1;Q.push(v);
- }
- }
- }
- return dep[t];
- }
- int dfs(int u,int flow)
- {
- if(u==t || !flow)return flow;
- for(int i=front[u];i!=-1;i=e[i].nxt)
- {
- int v=e[i].to;
- if(dep[v]==dep[u]+1 && e[i].w)
- {
- int di=dfs(v,min(flow,e[i].w));
- if(di)
- {
- e[i].w-=di;e[i^1].w+=di;
- return di;
- }
- else dep[v]=0;
- }
- }
- return 0;
- }
- int dinic()
- {
- int flow=0;
- while(bfs())
- {
- while(int d=dfs(s,Inf))flow+=d;
- }
- return flow;
- }
- int p,q;
- inline int gi(){int x;scanf("%d",&x);return x;}
- int main()
- {
- memset(front,-1,sizeof(front));
- n=gi();p=gi();q=gi();t=p+q+2*n+1;
- for(int i=1;i<=n;i++)
- Add(i+p,i+p+q+n,1);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=p;j++)
- {
- int opt=gi();
- if(opt)Add(j,i+p,1);
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=q;j++)
- {
- int opt=gi();
- if(opt)Add(i+p+q+n,j+p+n,1);
- }
- for(int i=1;i<=p;i++)Add(s,i,1);
- for(int i=1;i<=q;i++)Add(i+p+n,t,1);
- printf("%d\n",dinic());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2991047.html