ZKW费用流，双端队列优化SPFA。
#include<bits/stdc++.h> #define ll long long #define maxn 4005 #define inf 1<<30 using namespace std; int To[maxn],Laxt[maxn],Next[maxn],cap[maxn],cost[maxn],cnt=1; int N,S,T,ft,fc,st,sc,fee,dis[maxn]; ll ans; //费用 bool inq[maxn],vis[maxn]; deque<int>q; void add(int u,int v,int c,int cc){ Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;cap[cnt]=c;cost[cnt]=cc;} bool spfa() { memset(inq,0,sizeof(inq)); for(int i=0;i<=T;i++) dis[i]=inf; inq[T]=1; dis[T]=0; q.push_back(T); while(!q.empty()) { int u=q.front(); q.pop_front(); inq[u]=0; for(int i=Laxt[u];i;i=Next[i]) { int v=To[i]; if(cap[i^1]&&dis[v]>dis[u]-cost[i]) { dis[v]=dis[u]-cost[i]; if(!inq[u]){ inq[v]=1; if(q.empty()||dis[v]>dis[q.front()]) q.push_back(v); else q.push_front(v); } } } } return dis[S]<inf; } int dfs(int u,int flow) { vis[u]=1; if(u==T||flow==0) return flow; int tmp,delta=0; for(int i=Laxt[u];i;i=Next[i]) { int v=To[i]; if((!vis[v])&&cap[i]&&dis[v]==dis[u]-cost[i]) { tmp=dfs(v,min(cap[i],flow-delta)); delta+=tmp; cap[i]-=tmp; cap[i^1]+=tmp; } } return delta; } int main() { printf("%lld",ans); return 0; }