听说zkw比KM跑稠密图快很多
过来学习一个zkw继线段树后又一神作——zkw费用流
（虽然zkw线段树我还只会打模板orz）
其实就是利用了最短路的性质
dis[u]<=val(u,v)+dis[v] 当u在最短路上的时候取等号
修改dis值，即是将所有在增广路上的点u的dis加上一个delt，
而delt=min(dis[v]+w(u,v)-dis[u]) 其中u在增广路上，v不在.
和KM 一样，这样至少会多使一条边可增广，且不会破坏最短路的性质.
但其实就是背背背啊= =
树链剖分就是背背背
如今又要背背背
Orz
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; const int maxn=200010; int ans;//此处ans保存费用 int n,m,s,t; int first[maxn],to[maxn],next[maxn],caps[maxn],cost[maxn],cnt=-1; int vis[maxn],dis[maxn]; deque<int> dq; inline void add(int u,int v,int w,int c) { to[++cnt]=v; next[cnt]=first[u]; first[u]=cnt; caps[cnt]=w; cost[cnt]=c; } inline int afps(int s,int t)//反向spfa { memset(vis,0,sizeof(vis)); memset(dis,127,sizeof(dis)); dis[t]=0;vis[t]=1; //deque<int> dq; dq.clear(); dq.push_back(t); while(!dq.empty()) { int now=dq.front();dq.pop_front(); for(int i=first[now];i>-1;i=next[i]) if(caps[i^1] && dis[to[i]]>dis[now]-cost[i]) { dis[to[i]]=dis[now]-cost[i]; if(!vis[to[i]]) { vis[to[i]]=1; if(!dq.empty() && dis[to[i]]<dis[dq.front()])dq.push_front(to[i]); else dq.push_back(to[i]); } } vis[now]=0; } return dis[s]<2139062143; } inline int dfs(int u,int flow) { if(u==t){vis[t]=1;return flow;} int used=0,tmp;vis[u]=1; for(int i=first[u];i>-1;i=next[i]) if(!vis[to[i]] && caps[i] && dis[u]-cost[i]==dis[to[i]]) { tmp=dfs(to[i],min(caps[i],flow-used)); if(tmp)ans+=tmp*cost[i],caps[i]-=tmp,caps[i^1]+=tmp,used+=tmp; if(used==flow)break; } return used; } inline int zkw() { int maxflow=0; while(afps(s,t)) { vis[t]=1; while(vis[t]) { memset(vis,0,sizeof(vis)); maxflow+=dfs(s,2139062143); } } return maxflow; } int main() { memset(next,-1,sizeof next);memset(first,-1,sizeof first); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++){ int x,y,z,zz; scanf("%d%d%d%d",&x,&y,&z,&zz); add(x,y,z,zz); add(y,x,0,-zz); } printf("%d ",zkw());printf("%d",ans); }