网络流算法以及24题（未完结）
继续开坑，待填坑 （19/24）
感谢WC带我复习学习了网络流算法，这篇会讲到网络流当中最大流-最小割问题的Dinic算法，以及最小费用最大流的算法，如果有机会还会介绍有上下界的最大可行流等拓展问题
网络最大流（Dinic）
网络可以理解为一个带权的有向图，最简单的图是只有一个边权，代表流量。存在源点和汇点，分别用来输出流量和接受流量。网络最大流问题通俗来讲可以理解为，一个自来水厂，就是源点，和很多个住户中间节点，和一个排污口，就是汇点，这三者之前存在管道，管道对流量是有限制的，并且自来水厂没有入水管道，排污口没有出水管道，在此条件下，求最大的流量，这就是最本质的网络最大流问题
以此图为例
我们有一个贪心的做法，就是让每条边尽可能满流，对于下面这幅图我们可能存在这样的规划
这样是正确的吗？？未必是，请看图解
最大流是11，也就是说不一定满流才是最优的。
这样的话我们应该如何求解呢？引入反向边，意思就是我每次还是按照尽可能让每条边满流，如果流过去单位流量x，我们把反向边的容量调大，让它最多可以流回去x，如果存在更优解的情况，我们是可以通过反向边退回流量，也就是可以反悔。
然后接着再想流量怎么流过去，流过去的前提是容量未满，换句话说还有剩余流量。
然后介绍Dinic算法，先通过BFS构造分层图，按照可以流过去的情况确定深度deep，并且规定只有在相邻两边的deep相差为1时才可以流过去，然后通过dfs计算流量。之后重复bfs和dfs即可，直至没有可行方案
构造分层图例如
然后我们接下来按照满足尽可能满流和流量守恒的原则dfs求解，尽可能满流是指当流入量大于等于边的容量时，就让边满流过去，流量守恒是指当流入量小于边的容量时，需要流过去流入量的流量。
所以此次的最大流可能是27。这里跟dfs有关，是不确定的
此次dfs过后，我们会更新边权以及反向边的边权，此时边权代表的不是容量而是剩余容量，所以我们还可能存在可行流量，那么循环执行bfs，检查是否可行，不可行，退出输出即可
具体还是让我们看看代码吧，这次写注释了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5020;
int n,m,str,end,tot = -1;
int head[maxn],deep[maxn];
LL ans;
struct node
{
int to,net,va;
}data[maxn<<1];
void add(int x,int y,int va)
{
data[++tot].net = head[x];
data[tot].to = y;
data[tot].va = va;
head[x] = tot;
}
bool bfs()
{
memset(deep,0,sizeof(deep));//deep确定层数
deep[str] = 1;
queue<int> q;
q.push(str);
while(!q.empty())
{
int from = q.front();q.pop();
for(int i=head[from];i!=-1;i=data[i].net)
{
int to = data[i].to ;
int va = data[i].va ;
if(va&&(!deep[to]))//分层依据是没有到过并且还有容量
{
deep[to] = deep[from]+1;
q.push(to);
if(to==end)
return true;//如果to==end表示可以流到汇点，直接返回即可
}
}
}
return false;
}
LL dinic(int from,LL flow)
{
if(from==end)
return flow;//终止条件判断
LL rest = flow;//rest表示剩余的流量
for(int i=head[from];i!=-1;i=data[i].net)
{
int to = data[i].to ;
LL va = data[i].va ;
if(!rest)//如果都流完了可以提前返回
return flow;
if(va&&deep[to]==deep[from]+1)//可以流过去
{
LL k = dinic(to,min(rest,va));//流量守恒和尽可能满流原则
if(k==0)//流不过去，就调整为9，减少dfs的次数
deep[to] = 0;
data[i].va -= k;
data[i^1].va += k;
rest -= k;
//正向边剩余容量减去本次流过去的，反向边容量加上本次流过去的，用去了k个流量，剩余流量减去k
}
}
return flow - rest;//流过来的 = 流出去的 + 剩余的
}
int main()
{
scanf("%d%d%d%d",&n,&m,&str,&end);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b,va;
scanf("%d%d%d",&a,&b,&va);
add(a,b,va);
add(b,a,0);
//正向边容量为va，反向边的初始容量为0
}
while(bfs())//通过bfs检查是否可行
ans += dinic(str,2e9);//dfs统计答案
printf("%lld\n",ans);
return 0;
}有几个注意的问题
1.加边时tot和head[]的处置要设置成-1，因为之后取反向边的时候直接异或1即可，循环也要改成i ! = -1
2.注意对容量va的判断，不要写错
3.待补充
练习题
P1343 地震逃生
P2740 [USACO4.2]草地排水Drainage Ditches
最小费用最大流（SPFA + EK）
P3381 【模板】最小费用最大流
最小费用最大流问题是在一个流网络中，边不仅有容量限制，还有价格限制，表示单位流量的费用，求最小花费下的最大流
EK是单次寻找增广路的方法，规则也和上文的Dinic相似，只需要BFS和DFS即可。
对于最小费用最大流问题，我们先保证最小费用，因为最大流是可以通过EK一点点求出来的，当前花费最小肯定是最好的。所以用到了SPFA求解一条最短可行路，然后通过EK求出流量以及修改反向边等操作，直至SPFA无解即可
总上所述，与最大流相似的，我们还是要找增广路，但是我们不能全图增广了，主要是因为要找花费最小的，所以用SPFA代替了BFS的过程，只修改最短路径，反向边等操作是不变的
代码如下，依然有注释
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5020;
const int maxm = 50020;
int n,m,str,end,tot = -1,maxflow,mincost;
int head[maxn],pre[maxn],last[maxn],flow[maxn],d[maxn];
bool vis[maxn];
struct node
{
int net,va,cost,to;
}xuan[maxm<<1];
void add(int a,int b,int va,int cost)
{
xuan[++tot].cost = cost;
xuan[tot].net = head[a];
xuan[tot].to = b;
xuan[tot].va = va;
head[a] = tot;
}
bool SPFA()
{
memset(d,0x3f,sizeof(d));
memset(flow,0x3f,sizeof(flow));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(str);
vis[str] = 1;
d[str] = 0;
pre[end] = -1;
while(!q.empty())
{
int from = q.front();q.pop();
vis[from] = 0;
for(int i=head[from];i!=-1;i=xuan[i].net)
{
int to = xuan[i].to ;
int va = xuan[i].va ;
int cost = xuan[i].cost ;
if(va>0&&d[to]>d[from]+cost)
{//当前可行的要求是最短，容量也必须大于0
d[to] = d[from]+cost;
pre[to] = from;//前驱以及这个边记下来，因为要修改剩余容量
last[to] = i;
flow[to] = min(flow[from],va);//流过的容量
if(!vis[to])
{
vis[to] = 1;
q.push(to);
}
}
}
}
return pre[end] != -1;
}
void MCMF()
{
while(SPFA())
{
int now = end;
maxflow += flow[end];
mincost += flow[end]*d[end];
while(now!=str)
{
xuan[last[now]].va -= flow[end];
xuan[last[now]^1].va += flow[end];
now = pre[now];
}
//以流到end的流量为准，根据前驱依次经过来过的路，修改反向流量即可
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&str,&end);
for(int i=1;i<=m;i++)
{
int a,b,va,cost;
scanf("%d%d%d%d",&a,&b,&va,&cost);
add(a,b,va,cost);
add(b,a,0,-cost);//费用需要是负数，因为这算退费啊
}
MCMF();
printf("%d %d",maxflow,mincost);
return 0;
}网络流24题题解
此外对于比较经典的网络流24题，我打算在今后的学习中做一份题解，为了保持一个友好的篇幅，已更新的题解我会在这里以链接的方式给出来
最大流问题
P2756 飞行员配对方案问题 二分图最大匹配
P3254 圆桌问题 多对多匹配，输出方案
P2763 试题库问题 多对多匹配，输出方案
P2766 最长不下降子序列问题 dp + 分层图构建 + 拆点
P4011 孤岛营救问题 状态压缩 + BFS
P2761 软件补丁问题 状态压缩 + SPFA
P2765 魔术球问题 拆点 + 合理利用残余网络
P2754 [CTSC1999]家园 / 星际转移问题 分层图
P2764 最小路径覆盖问题 转化问题，合并点
P2774 方格取数问题 转化为最小割
费用流问题
P4016 负载平衡问题 转运需要付费，最大流等于总和，边权限制平均值
P4014 分配问题 效率为费用，二分图最大流
P3356 火星探险问题 图上连边，要求输出路径