这是没优化的
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')
{
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return s*w;
}
const int inf=1<<28;
struct node{
int to,nxt,w;
}e[1000001];
int head[200005];
int cur[200005];
int cnt=1;
int m,n,p,q;
queue<int > qq;
void add(int x,int y,int z)
{
e[++cnt].to=y;
e[cnt].w=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
int s,t;
int maxflow;
int d[200005],gap[200005];
void bfs()
{
for(int i=0;i<=n+1;i++)
{
d[i]=-1;gap[i]=0;
}
d[t]=0;
gap[s]=1;
qq.push(t);
while(!qq.empty())
{
int x=qq.front();
qq.pop();
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(d[y]!=-1)
continue;
d[y]=d[x]+1;
gap[d[y]]++;
qq.push(y);
}
}
return;
}
int dfs(int x,int flow)
{
if(x==t)
{
maxflow+=flow;
return flow;
}
int used=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(d[x]==d[y]+1&&e[i].w)
{
int mi=dfs(y,min(flow-used,e[i].w));
if(mi)
{
e[i].w-=mi;
e[i^1].w+=mi;
used+=mi;
}
if(flow==used)
return used;
}
}
--gap[d[x]];
if(!gap[d[x]])
d[s]=n+1;
d[x]++;
gap[d[x]]++;
return used;
}
int main()
{
m=read();
p=read();
q=read();
s=0;
n=p+q+m+m+1;
t=n;
for(int i=1;i<=m;i++)
{
add(p+i,p+i+m,1);
add(p+i+m,p+i,0);
for(int j=1;j<=p;j++)
{
int pd=read();
if(!pd)
continue;
add(j,i+p,1);
add(i+p,j,0);
}
}
for(int i=1;i<=p;i++)
{
add(s,i,1);
add(i,s,0);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=q;j++)
{
int pd=read();
if(!pd)
continue;
add(p+m+i,p+m+m+j,1);
add(p+m+m+j,p+m+i,0);
}
}
for(int i=1;i<=q;i++)
{
add(p+m+m+i,t,1);
add(t,p+m+m+i,0);
}
bfs();
while(d[s]<n)
{
memcpy(cur,head,sizeof(head));
dfs(s,inf);
}
printf("%d",maxflow);
}
```
by six_小6猪 @ 2021-04-21 07:30:36
？
by six_小6猪 @ 2021-04-21 07:30:50
当前负优化当然会负优化啊（
by c2020HXW @ 2021-04-21 07:32:13
@[c2020HXW](/user/89561) ??
by six_小6猪 @ 2021-04-21 07:34:02
这个东西很玄学吧，有些图边比较稀疏的就没有用的必要，因为每次向外流都流满了，而且还会增加一点memcpy常数上的影响。
by RedreamMer @ 2021-04-21 07:35:26
对于二分图和一些边流量为1的图随便用不用吧
by RedreamMer @ 2021-04-21 07:36:27
@[RedreamMer](/user/184549) 您的意思是memcpy的常数给我优化抵消了，就成负优化了？
by six_小6猪 @ 2021-04-21 07:39:50
@[six_小6猪](/user/191993) 额，重点不是这个，是在这类特殊图里面当前弧优化基本没有效果
by RedreamMer @ 2021-04-21 07:42:22
小边怎么着跑的都少，没太大必要
by logfk @ 2021-04-21 07:44:51
@[RedreamMer](/user/184549) 明白了，谢谢
by six_小6猪 @ 2021-04-21 07:48:36