费用流封装版
cpp
struct Flow{
int n,S,T,idx;
vector<int> h,e,f,w,ne;
vector<int> dis,cur,height;// d表示最短距离,cur为当前弧,height为势能函数
vector<bool> vis;
Flow(){}
Flow(int n){
init(n);
}
void init(int n,int S=0,int T=0){
h.assign(n+1,-1);
dis.assign(n+1,0);
cur.assign(n+1,0);
height.assign(n+1,0);
vis.assign(n+1,0);
e.clear();
ne.clear();
f.clear();
w.clear();
idx=0;
this->n=n;
this->S=S;
this->T=T==0?n:T;
}
void newEdge(int x=2){
for(int i=0;i<x;i++){
e.emplace_back();
ne.emplace_back();
f.emplace_back();
w.emplace_back();
}
}
void addEdge(int a,int b,int c,int d){
newEdge();
e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool dijk(){
for(int i=0;i<=n;i++)dis[i]=INF,cur[i]=h[i];
priority_queue<PII,vector<PII>,greater<>> pq;
dis[S]=0;
pq.emplace(0,S);
while(!pq.empty()){
auto [d,u]=pq.top();
pq.pop();
if(dis[u]!=d)continue;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
dis[v]=d+height[u]-height[v]+w[i];
pq.emplace(dis[v],v);
}
}
}
return dis[T]!=INF;
}
int find(int u,int limit){
if(!limit||u==T)return limit;
int flow=0;
vis[u]=1;
for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
int v=e[i];
if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
int t=find(v,min(f[i],limit-flow));
f[i]-=t,f[i^1]+=t,flow+=t;
if(flow==limit)break;
}
}
vis[u]=0;
return flow;
}
void mcmf(int &flow,int &cost){
flow=cost=0;
int r;
while(dijk()){
int r=find(S,INF);
flow+=r;
for(int i=0;i<=n;i++)height[i]+=dis[i];
cost+=height[T]*r;
}
}
};