有负权环的费用流直接跑EK会死循环，根据消圈定理：该最小费用流最后的残余网络不存在负权环。
可以提前消去负权环，
bool clear_circle(int &cost){
memset(cnt,0,sizeof cnt);
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
memset(mark,0,sizeof mark);
int hh = 0,tt = 1;
q[0] = S,d[S] = 0;
while(hh!=tt){
int u = q[hh++];
if(hh == N)hh = 0;
vis[u] = false;
for(int i = h[u];~i;i=ne[i]){
int j = e[i];
if(f[i] && d[j]>d[u]+w[i]){
cnt[j] = cnt[u] + 1;
d[j] = d[u] + w[i];
pre[j] = i;
if(cnt[j]>=n+2){
int t = j;
while(!mark[t]){
mark[t] = true;
t = e[pre[t]^1];
}
bool flg = true;
int mx = 1e9;
for(int i = t;flg || i!=t;i=e[pre[i]^1]){
flg = false;
// cout<<i<<" "<<e[pre[i]^1]<<" "<<w[i]<<'\n';
mx = min(mx,f[pre[i]]);
// f[pre[i]]-=1;
// f[pre[i]^1]+=1;
// cost += w[pre[i]];
}
flg = true;
for(int i = t;flg || i!=t;i=e[pre[i]^1]){
flg = false;
// cout<<i<<" "<<e[pre[i]^1]<<" "<<w[i]<<'\n';
f[pre[i]]-=mx;
f[pre[i]^1]+=mx;
cost += mx*w[pre[i]];
}
return true;
}
if(!vis[j]){
q[tt++] = j;
if(tt == N)tt = 0;
vis[j] = true;
}
}
}
}
return false;
}
View Code
详细如上
标签：费用,cnt,int,流消圈,memset,mark,hh,sizeof,定理 From： https://www.cnblogs.com/wanghai673/p/16774899.html