跟题解对拍了很多组数据,都是对的,但是交上去全WA了QAQ
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=2e4+10,INF=1e15;
struct EDGE{
int to,next,flow,cap;
}edge[M<<2];
int head[M],cnt=0;
void add(int u,int v,int flow,int cap){
edge[cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].flow=flow;
edge[cnt].cap=cap;
head[u]=cnt;
cnt++;
}
int T;
int a,b,c;
int s=1,t=2;
int dep[M],cur[M];
bool vis[M];
bool bfs(){
memset(dep,0,sizeof dep);
memset(vis,false,sizeof vis);
queue<int>q;
q.push(s);
dep[s]=1;
vis[s]=true;
while(!q.empty()){
int u=q.front();
cur[u]=head[u];
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]&&edge[i].flow<edge[i].cap){
dep[v]=dep[u]+1;
vis[v]=true;
q.push(v);
}
}
}
return vis[t];
}
int dfs(int u,int in){
if(u==t||in==0)return in;
int flow=0;
for(int i=cur[u];i!=-1;i=edge[i].next){
cur[u]=i;
int v=edge[i].to;
if(dep[v]==dep[u]+1&&edge[i].flow<edge[i].cap){
int f=dfs(v,min(in,edge[i].cap-edge[i].flow));
if(f>0){
edge[i].flow+=f;
edge[i^1].flow-=f;
flow+=f;
in-=f;
if(in==0)break;
}
}
}
return flow;
}
int Dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,INF);
// cout<<endl;
}
return ans;
}
map<int,bool>pd;
signed main(){
// freopen("a.txt","r",stdin);
cin>>T;
while(T--){
scanf("%lld%lld%lld",&a,&b,&c);
memset(head,-1,sizeof head);
memset(cur,-1,sizeof cur);
pd.clear();
cnt=0;
a+=2,b+=2,c+=2;
for(int i=3;i<=a;i++){
for(int j=3;j<=b;j++){
for(int k=3;k<=c;k++){
int x;
scanf("%lld",&x);
if(x==1){
if(!pd[(s<<20)+i]){
add(s,i,0,1);
add(i,s,0,0);
pd[(s<<20)+i]=true;
}
if(!pd[(i<<20)+j+a]){
add(i,j+a,0,1);
add(j+a,i,0,0);
pd[(i<<20)+j+a]=true;
}
if(!pd[((j+a)<<20)+j+a+b+c]){
add(j+a,j+a+b+c,0,1);
add(j+a+b+c,j+a,0,0);
pd[((j+a)<<20)+j+a+b+c]=true;
}
if(!pd[((j+a+b+c)<<20)+k+a+b]){
add(j+a+b+c,k+a+b,0,1);
add(k+a+b,j+a+b+c,0,0);
pd[((j+a+b+c)<<20)+k+a+b]=true;
}
if(!pd[((k+a+b)<<20)+t]){
add(k+a+b,t,0,1);
add(t,k+a+b,0,0);
pd[((k+a+b)<<20)+t]=true;
}
}
}
}
}
printf("%lld\n",Dinic());
}
return 0;
}