洛谷P1343地震逃生_Dinic

洛谷P1343最大流问题的Dinic解法，bfs分层然后dfs增广，还得捋捋弧优化

因为在Dinic算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把head数组复制一份，但不断更新增广的起点。

---

UPD:原来是这里写错了 ```cpp for(int eg=hd[p];eg;eg=e[eg].nxt) ``` 应该是 ```cpp for (int eg = cur[p]; eg && r; eg = e[eg].nxt) ``` 于是对于每次dfs完之后，cur数组指向该点上次dfs的边下标 ```cpp const int N=2e3+86; struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1; void add(int u,int v,int w){ e[++tot]=(edge){v,hd[u],w}; hd[u]=tot; } int n,m,x,lv[N];

int bfs(){
memset(lv,0,sizeof(lv));
memcpy(cur, hd, sizeof(hd)); // 当前弧优化初始化
queue q;
q.push(1);
lv[1]=1;
while(!q.empty()){
int p=q.front();
q.pop();
for(int eg=hd[p];eg;eg=e[eg].nxt){
int to=e[eg].to,vol=e[eg].w;
if(vol&&!lv[to]){
lv[to]=lv[p]+1,q.push(to);
}
}
}
return lv[n];
}

int dfs(int p,int flow){
if(p==n)
return flow;
int r=flow;
for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
cur[p]=eg;
int to = e[eg].to, vol = e[eg].w;
if(vol&&lv[to]==lv[p]+1){
int c=dfs(to,min(r,vol));
r-=c;
e[eg].w-=c;
e[eg^1].w+=c;
}
}
return flow-r;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>x;
f(i,1,m){
int aa,bb,cc;
cin>>aa>>bb>>cc;
add(aa,bb,cc);
add(bb,aa,0);
}
LL ans=0;
while(bfs()){
ans+=dfs(1,3e8);
}
if(ans)cout<<ans<<” “<<(x-1)/ans+1;
else cout<<”Orz Ni Jinan Saint Cow!”;
return 0;
}
```