在bfs的时候不需要把整张图bfs一遍，只要能到汇点就行了吧。。还有个东西叫当前弧优化。。
by Trick_t @ 2018-12-15 07:45:02
@[Trick_t](/space/show?uid=40059) 他加了当前弧
by SSerxhs @ 2018-12-15 08:00:22
你的当前弧优化满流没有return
by SSerxhs @ 2018-12-15 08:00:50
> @[我没有开挂](/space/show?uid=112008) $Dinic$ 没有优化的时候那是一级的慢好吗 (我可能得了狼抓兔子的后遗症)
by arfa @ 2018-12-15 08:08:46
@[我没有开挂](/space/show?uid=112008) 你加个当前弧优化啊……
改两行代码就行
in `dfs`
```
for(re int i=first[u] ...
->
for(re int &i=cur[u] ...
```
int `maxflow`
```
while(bfs(st,ed))
ans+=dfs(st,INF,ed);
->
while(bfs(st,ed))
memcpy(cur,first,sizeof(first),ans+=dfs(st,INF,ed);
```
by VenusM1nT @ 2018-12-15 08:14:50
【妈耶后遗症 in又打成了int】
by VenusM1nT @ 2018-12-15 08:15:16
我不明白大佬们为什么要用网络流，这不就是道贪心吗
by nofall @ 2018-12-15 08:16:22
@[Venus](/space/show?uid=23243) 然而我改了后变成了536ms
by 我没有开挂 @ 2018-12-15 08:41:07
@[我没有开挂](/space/show?uid=112008) 噗
这是为啥……
不然你看下我代码（这题我交了10次左右……挺卡时间的 这一份45ms）
```cpp
#include<bits/stdc++.h>
using namespace std;
queue <int> q;
int cnt=1,fst[100005],cur[100005],nxt[500005],to[500005],w[500005];
int n,m,dep[100005],S,T;
void AddEdge(int u,int v,int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
}
bool Bfs(int x)
{
memset(dep,0,sizeof(dep));
q.push(x);
dep[x]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(w[i] && !dep[v])
{
q.push(v);
dep[v]=dep[u]+1;
}
}
}
return dep[T];
}
int Dfs(int u,int flow)
{
if(u==T || !flow) return flow;
int used=0;
for(int i=cur[u];i;i=nxt[i])
{
cur[u]=i;
int v=to[i];
if(used==flow) return flow;
if(dep[v]==dep[u]+1 && w[i])
{
int fl=Dfs(v,min(flow,w[i]));
if(fl)
{
used+=fl;
flow-=fl;
w[i]-=fl;
w[i^1]+=fl;
if(!flow) break;
}
}
}
return used;
}
int Dinic()
{
int sum=0;
while(Bfs(S))
{
for(int i=0;i<=T;i++) cur[i]=fst[i];
sum+=Dfs(S,2147400000);
}
return sum;
}
int main()
{
int sum=0;
scanf("%d %d",&m,&n);
S=0;
T=n+m+1;
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
sum+=x;
AddEdge(S,i,x);
AddEdge(i,S,0);
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
AddEdge(m+i,T,x);
AddEdge(T,m+i,0);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
AddEdge(i,j+m,1);
AddEdge(j+m,i,0);
}
}
int ans=Dinic();
if(ans==sum)
{
printf("1\n");
for(int i=1;i<=m;i++)
{
for(int j=fst[i];j;j=nxt[j])
{
int v=to[j];
if(v>m && v<T && !w[j]) printf("%d ",v-m);
}
printf("\n");
}
}
else printf("0\n");
return 0;
}
```
by VenusM1nT @ 2018-12-15 08:42:51
@[Venus](/space/show?uid=23243) 我知道了,我手残打掉了半句话:
我的dfs中满流忘记return了,应该是for(re int i=first[u];~i&&add!=flow;i=e[i].next)
不过也感谢dalao们的帮助了
by 我没有开挂 @ 2018-12-15 08:49:42