# 自己寫了個最小費用最大流的模板

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
typedef long long ll;

double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();

struct network_flows
{
vector<ll> e;
vector<ll> pre;
vector<ll> vis;
vector<vector<ll> > cw;
vector<vector<ll> > ce;
vector<double> f;
vector<double> u;
vector<vector<double> > c;
vector<vector<double> > p;
deque<ll> q;

void clear_flow()
{
e.clear();
pre.clear();
vis.clear();
f.clear();
u.clear();
}

void clear_edge()
{
clear_flow();
cw.clear();
ce.clear();
c.clear();
p.clear();
}

ll size()
{
return cw.size();
}

void set_size(ll size_v)
{
clear_edge();
cw.resize(size_v);
ce.resize(size());
c.resize(size());
p.resize(size());
}

void add_edge(ll x,ll y,double c_v,double p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

void prepare(ll s,ll t)
{
clear_flow();
f.resize(size(),0);
f[s]=oo_max;
e.resize(size(),-1);
u.resize(size(),oo_max);
u[s]=0;
pre.resize(size(),-1);
pre[s]=s;
vis.resize(size(),0);
}

ll bfs(ll s,ll t,double &flow,double &cost)
{
prepare(s,t);
for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
{
ll now=q.front();
for (ll i=0;i<cw[now].size();i++)
if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
flow=f[t];
cost=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
{
double temp_flow,temp_cost;
while (bfs(s,t,temp_flow,temp_cost))
{
for (ll i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
flow+=temp_flow;
if (typ==0)
cost+=temp_cost;
else if (typ==1)
cost+=(temp_flow*temp_cost);
}
}
};
};
``````