WA on Test 4,答案2输出1
#include<bits/stdc++.h>
using namespace std;
using namespace std;
const int maxn=2e5+7;
int n,p,q,cnt=1,max_flow,s,t;
int head[maxn],dpt[maxn],cur[maxn];
struct node{
int v,w,nxt;
}e[maxn];
void add(int x,int y,int z){
e[++cnt].v=y;
e[cnt].w=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
bool bfs(){
queue<int>q;
memset(dpt,0,sizeof(dpt));
dpt[s]=1;
q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=e[i].nxt){
int y=e[i].v;
if(e[i].w&&dpt[y]==0){
q.push(y);
dpt[y]=dpt[now]+1;
if(y==t)return 1;
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t)return flow;
int res=flow,k;
for(int i=cur[x];i&&res;i=e[i].nxt){
int y=e[i].v;
cur[x]=i;
if(e[i].w&&dpt[y]==dpt[x]+1){
k=dfs(y,min(e[i].w,res));
if(k==0)dpt[y]=0;
e[i].w-=k;
e[i^1].w+=k;
res-=k;
}
}
return flow-res;
}
int main(){
cin>>n>>p>>q;
t=p+q+n+n+1;
for(int i=1;i<=p;i++){
add(s,i,1);
add(i,s,0);
}
for(int i=1;i<=q;i++){
add(p+n+n+i,t,1);
add(t,p+n+n+i,0);
}
for(int i=1;i<=n;i++){
add(p+i,p+n+i,1);
add(p+n+i,p+i,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=p;j++){
int x;
cin>>x;
if(x==1)
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;
cin>>x;
if(x==1)
add(p+n+i,p+n+n+j,1);
add(p+n+n+j,p+n+i,0);
}
}
int flow=0;
while(bfs()){
for(int i=0;i<=t;i++)
cur[i]=head[i];
while(flow=dfs(s,1<<29))max_flow+=flow;
}
cout<<max_flow;
return 0;
}