1 条题解
-
0
#include<bits/stdc++.h> using namespace std; struct edge{int x,y,c,pre,other;}a[1110000];int alen,last[410],h[410],st,ed; void ins(int x,int y,int c){ a[++alen]=edge{x,y,c,last[x],alen+1};last[x]=alen; a[++alen]=edge{y,x,0,last[y],alen-1};last[y]=alen; } bool bh(){ memset(h,0,sizeof(h));h[st]=1; queue<int>Q;Q.push(st); while(!Q.empty()){ int x=Q.front(); for(int k=last[x];k>0;k=a[k].pre){ int y=a[k].y; if(h[y]==0&&a[k].c>0){ h[y]=h[x]+1; Q.push(y); } } Q.pop(); } return h[ed]>0; } int findflow(int x,int f){ if(x==ed)return f; int sx=0; for(int k=last[x];k>0;k=a[k].pre){ int y=a[k].y; if(a[k].c>0&&f-sx&&h[y]==(h[x]+1)){ int sy=findflow(y,min(a[k].c,f-sx)); a[k].c-=sy;a[a[k].other].c+=sy; sx=sx+sy; } } if(sx==0)h[x]=0; return sx; } int main(){ int n,p,q;scanf("%d%d%d",&n,&p,&q); alen=0;memset(last,0,sizeof(last)); st=p+q+2*n+1;ed=st+1; for(int i=1;i<=p;i++)ins(st,i,1); for(int i=1;i<=q;i++)ins(p+2*n+i,ed,1); for(int i=1;i<=n;i++)ins(p+i,p+n+i,1); for(int i=1;i<=n;i++){ for(int j=1;j<=p;j++){ int x; scanf("%d",&x); if(x==1){ ins(j,i+p,1); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=q;j++){ int x; scanf("%d",&x); if(x==1){ ins(i+n+p,j+n*2+p,1); } } } int ans=0;while(bh())ans+=findflow(st,0x3fffffff); printf("%d",ans); return 0; }
- 1
信息
- ID
- 402
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者