这里记录学习网络流时候学的知识

ISAP

下面是对于当年模仿WuY模板写的SAP的重新研究和解读

听说SAP的定义包含了dinic以及ISAP，SAP意义就是最短增广路算法

那这个应该叫做ISAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
struct EDGE
{
    int u,v,w;
};
const int MAXV=10000,MAXE=40000;
struct GRAPH
{
    EDGE edge[MAXE];
    int next[MAXE],first[MAXV],cnt,v=0;
    void init(int vv)
	{
        memset(first,-1,sizeof(first));
        cls(edge);cls(next);
        cnt=-1;v=vv;
    }
    void addedge(int u,int v,int w)
	{
        edge[++cnt].u=u;edge[cnt].v=v;
        edge[cnt].w=w;next[cnt]=first[u];
        first[u]=cnt;edge[++cnt].u=v;
        edge[cnt].v=u;edge[cnt].w=0;
        next[cnt]=first[v];first[v]=cnt;
    }
}graph;
bool visited[MAXV];
int SAP(int S,int T)
{
    static int current[MAXE],distance[MAXV],layer[MAXV],last[MAXV],pred[MAXV];
    rep(i,0,graph.v)
    {
        current[i]=graph.first[i];
        distance[i]=layer[i]=0;
    }
    queue<int> q;
    q.push(T);
    visited[T]=true;
    layer[0]++;
    while (!q.empty())//第一遍bfs求出初始距离标号 （但是这一段事实上只是个没大用的常数优化，我的板子里是略去的）
    {
        int x=q.front();
        for (int k=graph.first[x];k!=-1;k=graph.next[k])
        {
            int j=graph.edge[k].v;
            if (!visited[j])
            {
                q.push(j);
                visited[j]=true;
                distance[j]=distance[x]+1;
                layer[distance[j]]++;
            }
        }
        q.pop();
    }
    int i=S,now_flow=inf,total_flow=0;
    while (distance[S]<graph.v)//在不断更新distance的过程中，源点一旦被改到graph.v就说明已经没有增广路可走了
    {
    xxx:
        last[i]=now_flow;//存下当前dfs过程中到i为止的now_flow
        for (int k=current[i];k!=-1;k=graph.next[k])
        {
            int j=graph.edge[k].v;//j:to where
            if ((!graph.edge[k].w)||distance[i]!=distance[j]+1) continue;//判断允许弧和饱和弧
            current[i]=k;//当前弧，从i出发的情况中dfs到了哪条弧
            int cur_flow=graph.edge[k].w;//当前弧所允许的流量上限
            now_flow=min(cur_flow,now_flow);//now_flow 正在找的增广路的流量上限
            pred[j]=i;//记录pred[j]增广路中j的前驱节点是i，其实模拟了一个栈进行dfs
            i=j;
            if (i==T)//如果i是汇点
            {
                total_flow+=now_flow;//总流量+=找到的增广路的流量
                while (i!=S)//调整过程，把整条增广路的情况结算，并把i置回源点
                {
                    i=pred[i];
                    graph.edge[current[i]].w-=now_flow;//正向边-=now_flow
                    graph.edge[current[i]^1].w+=now_flow;//反向边+=now_flow
                }
                now_flow=inf;//将当前寻找的增广路流量初始化
            }
            goto xxx;//相当于dfs
        }
        //i的所有允许弧已经被dfs完了，且当前找增广路从源点一直找到i点的流量上限是last[i]
        int min_dis=graph.v-1,min_place=-1;
        for (int k=graph.first[i];k!=-1;k=graph.next[k])//从刚才dfs完的所有边当中找到distance（与汇点间的距离）最小的非零流量边
        {
            int j=graph.edge[k].v;//to where
            if (graph.edge[k].w&&distance[j]<min_dis)
            {
                min_dis=distance[j];
                min_place=k;
            }
        }
        current[i]=min_place;//重置当前弧
        layer[distance[i]]--;//distance为i的这层有用点数量--（因为i把属于当前distance的能跑的流量都跑满了，所以现在要更改它的distance）
        if (!layer[distance[i]]) break;//gap优化 即出现了断层，那么不可能再有任何增广路
        distance[i]=min_dis+1;//更新i的distance
        layer[distance[i]]++;//新layer的有用点数量++
        if (i!=S) {i=pred[i];now_flow=last[i];}//把i回退到前驱点，同时把now_flow改成递归至前驱点时的now_flow
    }
    return total_flow;
}

它不仅比较难写(其实代码长是因为我的变量名长且用的前向星而非队友们的vector)，而且效率上没有什么明显优势(据网络上的说法，除非应用多路增广优化才能大大提升效率，否则和dinic还是一个数量级)。但其实有板子的话写起来没比dinic麻烦多少，就用这个吧。

dinic

dinic相对isap其实慢一些，因为每次需要重新标号时都需要把整张图bfs一遍。主要思路就是bfs求标号->找当前标号情况下的所有增广路->bfs求标号……直到找不到。

最大权闭合子图

定义

一张有向图(网上没有找到它是否一定要是dag)中，每个点都有一个权值。定义闭合子图为一个点集和点集内所有点之间的边组成的图，满足若某个点在点集内，则它的后继点也在点集内。当点集的权值和最大时，称作最大权闭合子图。

求法

该问题事实上可以转化为最小割问题。从S对每一个正权点连一条流量为权值的边，从每个负权点对T连一条流量为权值绝对值的边，将点之间的边的流量设为正无穷，则原图除去最小割即为最大权闭合子图。

证明

  1. 割边的含义

    由于原图的边都是无穷大，那么割边一定是与S或T相连的。

    割掉S与x的边，表示不选择x点作为子图的点
    割掉x与T的边，表示选择x点为子图的点

    如果S与x有边，表示x存在子图中
    如果x与T有边，表示x不存在于子图中

  2. 只有S与T不连通，图才是闭合子图

    若S与T联通，则必然存在一组点x,y,使得S->x->y->T。则据1的定义，x存在于子图中，y不存在于子图中，则与闭合子图定义矛盾

  3. 只要S与T不连通，图即为闭合子图（求最小割的过程中）

    首先剩余的图必定为原图的子图。若某个正权点被选择了，则它指向的所有负权点必然没有被选择。对于正权点指向的别的正权点，最小割过程中将不会割去它(割去的操作只会减小流量而不会断流因此没有收益)

  4. 最小割为最优方案

    最小割=(不选的正权和+要选的负权绝对值和）
    最大权闭合子图=（正权和-不选的正权和-要选的负权绝对值和）=正权和-最小割
    因为正权和是定值，而最小割保证值最小，所以最大权闭合子图一定最优。

参考:https://my.oschina.net/u/4417528/blog/3943851

最小路径覆盖

定义

给定有向图$G=(V,E)$。设$P$是$G$的一个简单路（顶点不相交）的集合。如果$V$中每个顶点恰好在$P$的一条路上，则称$P$是$G$的一个路径覆盖。$P$中路径可以从$V$的任何一个顶点开始，长度也是任意的，特别地，可以为$0$。$G$的最小路径覆盖是$G$的所含路径条数最少的路径覆盖。

建模

将每个点拆成两个点，形成一张二分图。设$x$点拆成$x_1$与$x_2$两个点。则若原图中存在$x$到$y$的有向边，则添加一条$x1$指向$y2$的边。原图的点数减去新图的二分图最大匹配即为答案。

原理

首先，若不存在任何边，显然答案为原图点数。同时，把拆成的两个点$x_1$当作出点，$x_2$当作入点。当新图中有一个匹配，即意味着匹配中的某个$x_1$可以连到$y_2$，则原本的$pre\rightarrow x$以及$y\rightarrow nxt$($pre$和$nxt$表示已存在的在$x$结束/从$y$开始的路径，且可以为空)两条路径显然可以变为$pre\rightarrow x\rightarrow y\rightarrow nxt$一条路径，减少了一条，答案减一。而二分图匹配的定义表明了$x_1$无法指向多个入点，$x_2$也无法指向多个出点。

二分图最小点权覆盖

定义

一张二分图，要求每条边都有至少一个端点被选择，每个点都有一个点权，问符合要求的选择的最小点权和

建模

从S向二分图一边的点连容量为点权的边，从另一边的点向T连容量为点权的边，原本的边容量设为inf

原理

感性理解：显然

证明：好像不会什么优美的，可以尝试分类讨论举例证明？

二分图最大点权独立集

定义

一张二分图，连着边的点不能都选，每个点都有一个点权，问选择的最大点权和

建模

是二分图最小点权覆盖的对偶问题，将和减去二分图最小点权覆盖即为答案

原理

设初始方案为全都选，那么就会出现很多不符合要求的。去掉哪些可以使答案最优呢？可以发现每条边都至少要去掉两个端点的其中一个，且需要去掉的点权最小。这不就是二分图最小点权覆盖问题嘛！

SPFA-dinic 最小费用最大流

将dinic的bfs换成spfa来求得最小费用的增广路。没用isap是因为它很难在处理最小费用增广路的同时更新结点的layer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
const int MAXV=10001,MAXE=40001;
struct EDGE
{
    int u,v,w,cost;//w是流量
};
struct GRAPH
{
    EDGE edge[MAXE];
    int next[MAXE],first[MAXV],cnt,cur[MAXV];
    inline void init()
	{
        cnt=0;
        cls(edge);cls(next);
        memset(first,-1,sizeof(first));
    }
    inline void addedge(int u,int v,int w,int cost)
	{
        edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].cost=cost;next[cnt]=first[u];first[u]=cnt++;
        edge[cnt].u=v;edge[cnt].v=u;edge[cnt].w=0;edge[cnt].cost=-cost;next[cnt]=first[v];first[v]=cnt++;
    }
    int distance[MAXV],maxflow,mincost;
    bool vis[MAXV];//spfa中代表inqueue,dfs中代表是否在当前搜索的增广路中避免成环
    queue <int> qu;
    inline bool spfa(int s,int t)//代替dinic的BFS
	{
        memset(distance,0x3f,sizeof(distance));
        cls(vis);
        distance[s]=0;
        vis[s]=true;
        qu.push(s);
        while (!qu.empty())
        {
            int p=qu.front();
            qu.pop();
            int q=first[p];
            vis[p]=false;
            while (q!=-1)
            {
                if (edge[q].w&&distance[edge[q].v]>distance[p]+edge[q].cost)
                {
                    distance[edge[q].v]=distance[p]+edge[q].cost;
                    if (!vis[edge[q].v])
                    {
                        qu.push(edge[q].v);
                        vis[edge[q].v]=true;
                    }
                }
                q=next[q];
            }
        }
        if (distance[t]==inf) return false;
        return true;
    }
    int dfs(int now,const int &t,int flow)
	{
        if (now==t) {maxflow+=flow;return flow;}
        int sum=0;
        vis[now]=1;
        for (int q=cur[now];q!=-1;q=next[q])
        {
            if (!vis[edge[q].v]&&edge[q].w&&distance[edge[q].v]==distance[now]+edge[q].cost)
            {
                cur[now]=q;//当前弧优化
                int p=dfs(edge[q].v,t,min(flow-sum,edge[q].w));
                sum+=p;edge[q].w-=p;edge[q^1].w+=p;mincost+=p*edge[q].cost;
                if (sum==flow) break;//把能流的都流干净了
            }
        }
        vis[now]=false;
        return sum;
    }
    void dinic(int s,int t)
	{
        while (spfa(s,t))
        {
            memcpy(cur,first,sizeof(first));
            dfs(s,t,inf);
        }
    }
}graph;

最大权不相交路径

问题的定义不赘述，顾名思义。

建模

每个点拆成入点和出点，在入点和出点间连容量为1(若路径可以在点上相交则容量inf)费用为该点点权的边。每个点的出点向该点连出的边的到达点的入点连容量为1费用为0的边。S向题意中的起始点连边，题意中的终点向T连边。

最大权？若点权为正岂不是需要最大费用最大流？如何用dinic-spfa来解？

事实上 由于图是DAG，可以直接将边权取负。