1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
|
#include<queue> using namespace std; const int N=405,M=50050,INF=1<<25; int n,p,q,st,ed,head[N],d[N],cnt=0; struct {int to,next,flow,cap;} e[M]; queue<int> Q; inline int read() { register int x=0,t=1; register char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if (ch=='-') t=-1,ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t; } void add(int u,int v,int cap) { e[cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; e[cnt++].cap=cap; } int bfs(int s,int t) { while (!Q.empty()) Q.pop(); for(int i=1;i<=n*2+p+q+2;i++) d[i]=0; d[s]=1,Q.push(s); while (!Q.empty()&&!d[t]) { int x=Q.front();Q.pop(); for(int i=head[x];~i;i=e[i].next) { int to=e[i].to; if (e[i].flow<e[i].cap&&!d[to]) { d[to]=d[x]+1; Q.push(to); } } } return d[t]; } int dfs(int x,int t,int flow) { if (!flow||x==t) return flow; int ret=0,new_flow; for(int i=head[x];~i;i=e[i].next) { int to=e[i].to; if (d[x]+1==d[to]) { new_flow=dfs(to,t,min(flow,e[i].cap-e[i].flow)); e[i].flow+=new_flow; e[i^1].flow-=new_flow; ret+=new_flow; flow-=new_flow; } } return ret; } int Dinic(int s,int t) { int ret=0; while (bfs(s,t)) ret+=dfs(s,t,INF); return ret; } int main() { n=read(),p=read(),q=read(); st=n*2+p+q+1,ed=st+1; for(int i=1;i<=2*n+p+q+2;i++) head[i]=-1; for(int i=1;i<=p;i++) add(st,i,1),add(i,st,0); for(int i=n*2+p+1;i<=n*2+p+q;i++) add(i,ed,1),add(ed,i,0); for(int i=p+1;i<=p+n;i++) add(i,i+n,1),add(i+n,i,0); for(int i=1;i<=n;i++) for(int j=1;j<=p;j++) { int x=read(); if (!x) continue; add(j,p+i,1); add(p+i,j,0); } for(int i=1;i<=n;i++) for(int j=1;j<=q;j++) { int x=read(); if (!x) continue; add(p+n+i,n*2+p+j,1); add(n*2+p+j,p+n+i,0); } printf("%d",Dinic(st,ed)); return 0; }
|
近期评论