最小费用最大流
Dinic(费用流)
和 Dinic最大流 的最大的区别在于多了“费用”这一概念（所以不能随心所欲的“流”了）。
既然不能随心所欲的“流”了，那分层（找增广路的）的意义也不大了。所以就不用写 Bfs，取而代之的 Spfa（或者 Dij），思路变为每回找到花费最小的一条路，一条一条的找，不断更新即可。
在记录路径时，我们新开两个数组，一个负责存储流过来的节点是谁（类似于存父节点），另一个存储是从那条路流过来的（方便更新反向弧）。在最后更新流量时，通过不断的“爬树”即可。
注意：
由于多了“费用”，所以连反向边的时候，要将费用取反。
虽然要找最小费用，但前提是能流出最大流。
代码思路
加边（注意反向弧）。
判断汇点源点联通（同时计算联通的最小价值）。
累计价值和流量。
更新经过路径的流量。
输出最大流，最小费用。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
struct po{
int n_t;
int v;
int l;//流量
int c;//费用
}p_p[o_o];
int h_d[o_o],x_p=1;
int n=r_r(),m=r_r(),s=r_r(),t=r_r();
bool b_b[o_o];//标记是否重复访问节点（跑环）
int l_v[o_o];//节点剩余流量
int v_l[o_o];//到当前节点最小价值
int f_f[o_o];//存流向当前点的点
int l_t[o_o];//存流向当前点的边
int m_l,m_v;//最大流，最小花费
void a_d(int u,int v,int l,int c){//加边
p_p[++x_p].v=v;
p_p[x_p].l=l;
p_p[x_p].c=c;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
queue<int>q_q;
bool s_p(){
//初始化所有数组
memset(b_b,0,sizeof b_b);
memset(l_v,0x3f,sizeof l_v);
memset(v_l,0x3,sizeof v_l);
q_q.push(s);//源点入队
b_b[s]=1;//标记
v_l[s]=0;//价值初始化
f_f[t]=-1;
while(!q_q.empty()){
int k_k=q_q.front();
q_q.pop();
b_b[k_k]=0;//取消标记
for(int i=h_d[k_k];i;i=p_p[i].n_t){//枚举出边
int v=p_p[i].v;
if(p_p[i].l&&v_l[v]>v_l[k_k]+p_p[i].c){//有流量并且价值可以减小
v_l[v]=v_l[k_k]+p_p[i].c;//更新价值
f_f[v]=k_k;//记录来的点
l_t[v]=i;//记录来的边的编号
l_v[v]=min(l_v[k_k],p_p[i].l);//最多能流多少
if(!b_b[v]){//没有被标记过（不会跑环）
b_b[v]=1;//标记
q_q.push(v);//入队
}
}
}
}
return f_f[t]!=-1;//源点汇点是否联通
}
int main(){
for(int i=1;i<=m;i++){
int a=r_r(),b=r_r(),v=r_r(),c=r_r();//加边
a_d(a,b,v,c);
a_d(b,a,0,-c);//反向弧，注意花费取反
}
while(s_p()){//源点汇点联通，还有流量可流
int k_k=t;
m_l+=l_v[k_k];//累计流量
m_v+=l_v[k_k]*v_l[k_k];//累计价值
while(k_k!=s){//没有返回源点
p_p[l_t[k_k]].l-=l_v[t];//更新边的流量
p_p[l_t[k_k]^1].l+=l_v[t];//更新反向弧的流量
k_k=f_f[k_k];//跳上一级
}
}
printf("%d %d",m_l,m_v);//输出最大流，最小费用
return 0;
} 有负圈的费用流
思路
和普通的最小费用最大流的区别在于出现了“负圈”的情况。
而在上面的 Dinic 算法中，我们用到了 SPFA 来判最小花费，所以如果出现“负圈”，那么就会陷入死循环。
为了避免这种情况，我们可以先将所有的负边先流满，这样，它就和没有流满的正边的反向弧性质相同了，注意此时我们记录每个点的流量情况。可以让一些节点先“透支”一些流量，注意代价要记录结果。
现在，对于一些节点剩余的“量”是正数，而另一些是负数。这些值，我们肯定要处理的，这时，我们可以建两个新节点，一个新源点和所有大于零的节点连边（这样才能满足它们的“需求”），一个新汇点和所有小于零的节点连边（让它们多余的“流走”）。
这时通过新源点和新汇点跑一遍最大费用最小流，尽量满足不同节点的不同“需求”（此时已经不存在负边了，负边是越跑越划算的所以也是跑最小费用最大流）。因为我们一开始假设的是所有负边“流满”，而这之中可定有多余的（达不到最大流量的边），所以通过这次最大费用最小流来将这些“冗余”的“流量”除去。
满足尽量多的节点后，就可以将源点和汇点正常再跑一遍最小费用最大流了，因为还有一些没有“需求”的节点（没有负边的节点）需要统计。
代码思路
加边（注意反向弧）。
将所有负边“流满”，并记录节点状态和费用。
建新源点和新汇点，并和有需要的节点连边。
用新源点和新汇点跑一遍最小费用最大流，去除“冗余”。
在跑一遍真正的源点和汇点的最小费用最大流，统计结果，输出即可。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e5+10;
const int m_a=1e9+10;
struct po{
int n_t;
int v;
int l;//边的最大流量
int c;//“路费”
}p_p[o_o];
int x_p=1,h_d[o_o];
int v_l[o_o];//到当前节点最小价值
int l_t[o_o];//记录流到当前节点的路
int l_v[o_o];//最多能流的量
int s_m[o_o];//当前点剩余流量
bool b_b[o_o];//标记是否重复访问节点（跑环）
int m_l,m_v;//最大流量，最小花费
int s_i,t_i;//临时节点
int n=r_r(),m=r_r(),s=r_r(),t=r_r();
void a_d(int u,int v,int l,int c){//加边
p_p[++x_p].v=v;
p_p[x_p].l=l;
p_p[x_p].c=c;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
queue<int>q_q;
bool s_p(int s,int t){
memset(b_b,0,sizeof b_b);//标记是否重复访问节点（跑环）
memset(v_l,0x3f,sizeof v_l);//初始化流到当前节点的最小费用
q_q.push(s);
v_l[s]=0;//初始化费用
b_b[s]=1;//标记
l_v[s]=m_a;//初始化最多流的量
while(!q_q.empty()){
int k_k=q_q.front();
q_q.pop();
b_b[k_k]=0;//标记
for(int i=h_d[k_k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(p_p[i].l&&v_l[v]>v_l[k_k]+p_p[i].c){//有流量并且更新最小费用
v_l[v]=v_l[k_k]+p_p[i].c;//更新最小费用
l_t[v]=i;//记录流过来的路
l_v[v]=min(l_v[k_k],p_p[i].l);//最多能流的量
if(!b_b[v]){//标记是否重复访问节点（跑环）
b_b[v]=1;//标记
q_q.push(v);//入队
}
}
}
}
return v_l[t]!=v_l[0];//检查源点汇点是否联通
}
void u_p(int s,int t){
int k_k=t;
while(k_k!=s){//未回到原点
int i=l_t[k_k];//返回流过来的路
p_p[i].l-=l_v[t];//更新路径流量
p_p[i^1].l+=l_v[t];//更新流量
k_k=p_p[i^1].v;//回到流过来的点
}
m_l+=l_v[t];//统计流量
m_v+=l_v[t]*v_l[t];//统计费用
}
int main(){
for(int i=1;i<=m;i++){
int a=r_r(),b=r_r(),w=r_r(),c=r_r();//读入
//加边
if(c>=0){
a_d(a,b,w,c);
a_d(b,a,0,-c);//加反向弧
}else {//假设所有负边全部流完了
a_d(a,b,0,c);//流量清零
a_d(b,a,w,-c);//反向弧更新
s_m[a]-=w;//节点流量更新
s_m[b]+=w;//节点流量更新
m_v+=w*c;//统计费用流
}
}
s_i=n+1;//新源点
t_i=n+2;//新汇点
for(int i=1;i<=n;i++){
if(!s_m[i])continue;//没有流量跳过
if(s_m[i]>0){//节点需要流量
a_d(s_i,i,s_m[i],0);//和新源点连边（可以让“量”流过来）
a_d(i,s_i,0,0);//反向弧
}else {//节点不需要这些流量
a_d(i,t_i,-s_m[i],0);//和新汇点连边（可以让“量”流走）
a_d(t_i,i,0,0);//反向弧
}
}
//处理所有需求和多余有关的“流动”
while(s_p(s_i,t_i))u_p(s_i,t_i);//新节点流量
m_l=0;//初始化最大流量
//此时问题已经解决了，可以跑正常的最小费用最大流了
while(s_p(s,t))u_p(s,t);//真正流量计算
printf("%d %d\n",m_l,m_v);//输出最大流量，最小费用
return 0;
} 
