头像

Sata_星空


访客:1239

离线:7天前



前言:

$\qquad$ 图论的复习笔记,大体以模板为主。

$\qquad$ 这边 Latex 有点炸,原网址 https://xjx885.coding-pages.com/post/nEDVoSj5j/

$\qquad$ 建议与基础图论知识拓展 一起食用。


$~\$

正文:

$\qquad$ :由若干给定点和连接这些点之间的边组成的图形。

$\qquad$ 图的存储:邻接表/邻接矩阵,我习惯直接上 vector。

$\qquad$ 图上搜索:在图上进行的 DFS/BFS,可以(在时间无限的前提下)解决绝大多数问题,是骗分的好方法。

$\qquad$ 应用:求连通块,求无权图最短路等,应用不多,大多数时候配合其它算法一起使用。

$\qquad$ 有向无环图(DAG):没有环的有向图。

$\qquad$ 拓扑排序:对一张图上的节点按依赖关系排序的过程。

$\qquad$ 实现方法:求入度,找出入度为 $0$ 的点,拿出来放队列里,扫描队列,每扫到一个点,就把这个点连接的所有点入度 $-1$,如果入度为 $0$ 就往队列里放。队列中出现的节点的顺序就是拓扑排序后的顺序,如果有节点没入队,则图中有环。

$\qquad$ 应用:前面的点不依赖后面的点,故其排序结果可作为 DAG 上 DP 的递推顺序,有环图可先缩点再进行拓扑排序。

$~\$

  • 解析:题目保证了按所给边建出来的图是个 DAG,随便跑个拓扑排序就好了。设 $f(i)$ 表示以 $i$ 为终点最多能浏览多少城市,转移方程显然(方法不唯一,你要闲着无聊倒着来也是可以的)。

  • 代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read();

const int N = 1e5 + 10;

int n, m, ind[N], f[N];

queue <int > q;
vector <int > link[N];

void topo()
{
    for(register int k = 1; k <= n; k++)
        if(!ind[k]) q.push(k), f[k] = 1;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop();

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k];
            if(!(--ind[to])) q.push(to);
            f[to] = max(f[to], f[wz] + 1);
        }
    }
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read();
        link[u].push_back(v), ind[v]++;
    }

    topo();
    for(register int k = 1; k <= n; k++)
        printf("%d\n", f[k]);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$~\$

$\qquad$ 强连通:一张有向图 $G$ 强连通,意味着 $G$ 中任意两点都连通。

$\qquad$ 强连通子图:有一有向图 $G’ \subseteq G$,若 $G’$ 强连通,则 $G’$ 是 $G$ 的强连通子图。

$\qquad$ 强连通分量:极大的强连通子图。

$\qquad$ 强连通分量求法: Tarjan 算法。

$\qquad$ 实现:进行一种特殊的 DFS,如果在该 DFS 的过程中碰触到了特定节点,则从栈中找强连通分量(具体原理,实现方法不多讲,自行百度)。

$\qquad$ 代码:

void Tarjan(int wz)
{
    dfn[wz] = low[wz] = ++tot;
    in[wz] = 1, s.push(wz);

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int to = link[wz][k];
        if(!dfn[to])
            Tarjan(to), low[wz] = min(low[wz], low[to]);
        else if(in[to])
            low[wz] = min(low[wz], dfn[to]);
    }

    if(dfn[wz] == low[wz])
    {
        int p = ++color - 11451413;
        while(!s.empty() && p != wz)
            in[p = s.top()] = 0, col[p] = color, s.pop();
    }
}

$\qquad$ 应用:单独应用很少,甚至拓展出的割点和桥的应用也不多,所以不讲。这里讲一下拓展出的可以和上面的拓扑排序结合的缩点算法。

$\qquad$ 对每个点跑一遍 tarjan 后,缩点操作变得很简单,如果原图中存在边 $(u,v)$,则将 $u$ 所在的连通块与 $v$ 所在的连通块在新图上连边。

$\qquad$ 注意两点:首先,如果 $u,v$ 在同一个连通块内,则它们之间不需连边(题目特别要求除外),其次,我们最好避免重边,避免重边有很多方法,我常用的一种是后面代码里面的,直接暴力地开个 $set$,这适用于边数不多的情况,还有一种是建一个 bitset,依次让每一个连通块向其他连通块建边,建边后再 bitset 中打上标记,换到下一个连通块时清空标记即可,这种方法在复杂度上比较优秀。

$\qquad$ 缩点完之后就成了 DAG 了,就可以跑 topo 解决很多问题了。

$~\$

  • 解析:本题其实没必要用 topo,直接判有多少点出度为零就行了,不过后面的代码还是用了 topo。大概讲一下 topo 的思路:令 $f(i)(j)$ 表示 $j$ 号点(缩点后) 是否喜欢 $i$ 号点,转移的时候合并数组,最后判数组中是不是全是一就行了, $j$ 这一维可以用 bitset 维护,很方便 。 注意:有一种思路是这样的: 设 $f(i)$ 表示喜欢 $i$ 号点的人数,转移时加在一起,最后判人数是不是等于总人数。这种方案在树上是可行的,但 DAG 上不可行,因为两个点之间的路径不一定唯一,所以可能有点被重复计算了。

  • 代码:

#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

inline int read();

using namespace std;

const int N = 1e4 + 10;

int n, m, tot, color;
int dfn[N], low[N], col[N], in[N];

vector <int > link[N];
stack <int > s;

bitset <N > f[N];

void Tarjan(int wz)
{
    dfn[wz] = low[wz] = ++tot;
    in[wz] = 1, s.push(wz);

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int to = link[wz][k];
        if(!dfn[to])
            Tarjan(to), low[wz] = min(low[wz], low[to]);
        else if(in[to])
            low[wz] = min(low[wz], dfn[to]);
    }

    if(dfn[wz] == low[wz])
    {
        int p = ++color - 11451413;
        while(!s.empty() && p != wz)
            in[p = s.top()] = 0, col[p] = color, s.pop();
    }
}

vector <int > new_link[N];
queue <int > q;

int ind[N], ans;
set <pair <int , int > > built;

void topo()
{
    for(int k = 1; k <= color; k++) f[k][k] = 1;
    for(int k = 1; k <= color; k++) if(!ind[k]) q.push(k);

    while(!q.empty())
    {
        int wz = q.front();
        q.pop();

        for(int k = 0; k < (int )new_link[wz].size(); k++)
        {
            int to = new_link[wz][k];
            if(!(--ind[to])) q.push(to);
            f[to] |= f[wz];
        }
    }
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read();
        link[u].push_back(v);
    }

    for(register int k = 1; k <= n; k++)
        if(!dfn[k]) Tarjan(k);
    for(register int k = 1; k <= n; k++)
        for(int i = 0; i < (int )link[k].size(); i++)
        {
            int to = link[k][i];
            if(col[k] != col[to] && !built.count(make_pair(col[k], col[to])))
                new_link[col[k]].push_back(col[to]), ind[col[to]]++, built.insert(make_pair(col[k], col[to]));
        }


    topo();
    for(register int k = 1; k <= color; k++) f[0][k] = 1;
    for(register int k = 1; k <= n; k++)
        if(f[col[k]] == f[0]) ans++;
    printf("%d\n", ans);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\$

$\qquad$ 生成树: 取图中边集 $E’$ ,使得图中点集 $P$ 连通,且二者组成的新图 $G’$ 是一棵树,这棵新树是图 $G$ 的一种生成树。

$\qquad$ 最小生成树: $E’$ 的权值和最小的生成树。

$\qquad$ 算法:Kruskal 算法。(其它几个算法不咋常用,略过)

$\qquad$ 实现:把 $E$ 中所有边按权值排序,从小到大依次拿边,如果边两端未连通,则将该边计入答案,并连通两端,否则跳过。维护两个点之间是否连通可以使用并查集。

$~\$

  • 代码:
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e3 + 10;
const int M = 2e5 + 10;

int n, m, tot, ans, fa[N];

int find (int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct node
{
    int a, b, c;
    bool operator < (const node & other) const
    {
        return c < other.c;
    }
} edge[M];

inline int read();

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        fa[k] = k;
    for(register int k = 1; k <= m; k++)
        edge[k].a = read(), edge[k].b = read(), edge[k].c = read();
    sort(edge + 1, edge + 1 + m);

    for(register int k = 1; k <= m; k++)
    {
        if(tot == n - 1) break;
        int a = edge[k].a, b = edge[k].b, c = edge[k].c;
        if(find(a) != find(b))
            ans += c, fa[fa[a]] = fa[b], tot++;
    }

    if(tot == n - 1) printf("%d\n", ans);
    else puts("orz");

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$\qquad$ 最小生成树也很少单独考,主要还是和其它图论知识点混在一起丢给考生。

$\qquad$ 拓展: 次小生成树和严格次小生成树,思路是一样的:先跑出最小生成树,然后遍历所有未被选中的边 $(u,v,d)$ ,用倍增跑出树上 $u,v$ 之间的最长边(严格次小生成树还要严格次小边),然后拿枚举的边替换跑出来的边就好,取权值总和最小值。

$\qquad$ 代码不放了,没啥难度的操作,但是码量还是有的(尤其是严格次小生成树)。

$~\$

$\qquad$ 最短路:从 $E$ 中选取一条路径 $R$ 使 $u,v$ 两点连通,求 $R$ 最小边权和。

$\qquad$ 算法: Floyd,SPFA,Dijkstra 。

$\qquad$ Floyd 主要用于求任意两点间的最短路,复杂度 $O(n^3)$。

$\qquad$ SPFA 可以用在稀疏图上,稠密图一般也可以,复杂度玄学,上界为 $O(nm)$。

$\qquad$ Dij 只能用在正权图上,可并堆优化后复杂度是稳定的 $O(nlogn)$。

$\qquad$ 下面只放模板,扩展可以看我的另一篇博文:基础图论知识拓展

$~\$

  • 代码:
// Floyd

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read();

const int N = 210;
int n, f[N][N];

signed main()
{
    n = read();
    memset(f, 0x3f, sizeof(f));
    for(register int k = 1; k <= n; k++)
        for(int i = k + 1; i <= n; i++)
            f[k][i] = read();

    for(register int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(k != i && i != j && k != j)
                    if(f[i][k] + f[k][j] < f[i][j])
                        f[i][j] = f[i][k] + f[k][j];
    printf("%d", f[1][n]);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

// SPFA

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read();

const int N = 210;

queue <int > q;
int n, dis[N], in[N];

struct node
{
    int to, len;
    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};
vector <node > link[N];

void SPFA()
{
    memset(dis, 0x3f, sizeof(dis));
    q.push(1), in[1] = 1, dis[1] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = 0;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis[wz] + len < dis[to])
            {
                dis[to] = dis[wz] + len;
                if(!in[to]) in[to] = 1, q.push(to);
            }
        }
    }
}

signed main()
{
    n = read();
    for(register int k = 1; k <= n; k++)
        for(int i = k + 1; i <= n; i++)
        {
            int x = read();
            link[k].push_back(node(i, x));
        }

    SPFA(), printf("%d\n", dis[n]);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

// Dij

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read();

const int N = 210;

#define mp make_pair
#define P pair<int ,int >

priority_queue <P, vector <P>, greater<P> > q;
int n, dis[N], sol[N];

struct node
{
    int to, len;
    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};
vector <node > link[N];

void dij()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0, sol[1] = 0, q.push(mp(0, 1));

    while(!q.empty())
    {
        int wz = q.top().second;
        q.pop();

        if(sol[wz]) continue;
        sol[wz] = 1;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis[wz] + len < dis[to])
            {
                dis[to] = dis[wz] + len;
                q.push(mp(dis[to], to));
            }
        }
    }
}

signed main()
{
    n = read();
    for(register int k = 1; k <= n; k++)
        for(int i = k + 1; i <= n; i++)
        {
            int x = read();
            link[k].push_back(node(i, x));
        }

    dij(), printf("%d\n", dis[n]);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$\qquad$ 欧拉通路:通过图中所有边恰一次并经过所有顶点的通路。

$\qquad$ 欧拉回路:通过图中所有边恰一次并经过所有顶点并回到起点的通路。

$\qquad$ 简单的说,欧拉通路是一笔画,欧拉回路要求你一笔画完之后还能回到起点。

$\qquad$ 有欧拉通路的无向图叫半欧拉图,有欧拉回路的无向图叫欧拉图。

$\qquad$ 性质: $G$ 是欧拉图等价于 $G$ 没有奇度顶点。 $G$ 是半欧拉图等价于 $G$ 仅有 2 奇度顶点。

$\qquad$ 没啥大用…不放解法和例题了,有兴趣可以去 OI-wiki 上看。

$~\$

$\qquad$ 差分约束系统:由 $m$ 个形如 $x_i-x_j\le c_k$ 的不等式组成的 $n$ 元一次不等式组,例如下面这个。

$$x1-x2\le 1$$
$$x2-x3\le 4$$
$$x3-x4\le 2$$

$\qquad$ $x1-x4$ 最大值怎么求?很简单,全部加起来就完了…但如果中间某些式子的形式变一下,并且式子变得很多呢?让电脑去移项转换?

$\qquad$ 不需要那么麻烦,我们观察式子的形式: $x_i-x_j\le c_k$,形似我们最短路中的 $dis_i-dis_j \le len(i,j)$。

$\qquad$ 所以我们可以通过最短路的松弛操作解决差分约束问题,具体方案是:如果我们要求 $x_n-x_1$ 的最大值,就把式子整理成 $x_j-x_i\le k$ 的形式,从 $i$ 向 $j$ 连边权为 $k$ 的边,跑最短路,如果我们要求 $x_n-x_1$ 的最小值,就把式子整理成 $x_j-x_i \ge k$ 的形式,从 $i$ 向 $j$ 连边权为 $k$ 的边,跑最长路。

$\qquad$ 如果最短路/最长路有负环/正环,则结果不存在,若 $1,n$ 不连通,则结果为无穷小/大。

$\qquad$ 注意:小于号要通过减一换成小于等于,大于号要同样换成大于等于,等于号可以换成两个式子,一个大于等于,一个小于等于。

$~\$

  • 解析:模板题,照着上面说的建边跑最SPFA就好,注意:题目还有隐含不等式,任意两点间最多只能种一棵树,最少要种零棵树。

  • 代码:

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read();

const int N = 3e4 + 10;

struct node
{
    int to, len;
    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};
vector <node > link[N];

void add_edge(int u, int v, int w)
{
    link[v].push_back(node(u, w));
}

int n, m, dis[N], in[N];
queue <int > q;

void SPFA()
{
    memset(dis, 0xef, sizeof(dis));
    q.push(0), in[0] = 1, dis[0] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = 0;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis[wz] + len > dis[to])
            {
                dis[to] = dis[wz] + len;
                if(!in[to]) q.push(to), in[to] = 1;
            }
        }
    }
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        add_edge(k - 1, k, -1);
    for(register int k = 1; k <= n; k++)
        add_edge(k, k - 1, 0);
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read(), w = read();
        add_edge(v, u - 1, w);
    }

    SPFA(), printf("%d", dis[n]);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$\qquad$ 2-SAT 问题:给出 $n$ 个二元组和若干矛盾信息 $(x_i,y_j)$,求从每个二元组中选一个元素且选出元素互不矛盾的方案。

$\qquad$ 解决方案:以两组二元组 $(x_1,y_1),(x_2,y_2)$ 为例,若 $x_1$ 与 $y_1$ 矛盾,则选了 $x_1$ 就必须选 $y_2$,选了 $y_1$ 就必须选 $x_2$,其它元素间没有确定关系。

$\qquad$ 我们把各个元素抽象成点,把元素间这种“选了我就必须选他” 的关系视作有向边,则一个 2-SAT 问题被抽象成了一张有向图,我们可以对有向图进行缩点,一个强连通分量内的点必定一起选,若一个二元组的两个元素在同一个强连通分量内,则该 2-SAT 无解,否则有解。缩点后生成一张 DAG,对于一条有向边 $(u,v)$,若选 $u$ 则必选 $v$,若选 $v$ 则不一定选 $u$,所以如果一个二元组的两个点可达,则 “在前面($u$)” 的点一定不选,而所谓 “在前面”,表现为拓扑序更小,也就是说拓扑序小的节点不选。如果两个点不可达?那就随便选好了。

$\qquad$ 所以整体思路是缩点+topo,但实际上不需要 topo,tarjan 求出来的连通块编号(我代码中的 $col$)本质上就是一个反拓扑序,所以可以直接代替 topo 序使用(其实不用管是什么序的,先随便打个大于号,如果答案反了就改成小于号就好)。

  • 解析:把一个变量的真假看做二元组的两个元素,套板子即可。

  • 代码:

#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e6 + 10;

int n, m, color, tot;
int dfn[N], low[N], col[N], in[N];
vector <int > link[N];
stack <int > s;

void tarjan(int wz)
{
    dfn[wz] = low[wz] = ++tot;
    in[wz] = 1, s.push(wz);

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int to = link[wz][k];
        if(!dfn[to])
            tarjan(to), low[wz] = min(low[wz], low[to]);
        else if(in[to])
            low[wz] = min(low[wz], dfn[to]);
    }

    if(dfn[wz] == low[wz])
    {
        int t = ++color - 114514191;
        while(!s.empty() && t != wz)
            t = s.top(), s.pop(), col[t] = color, in[t] = 0;
    }
}

inline int read();

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= m; k++)
    {
        int i = read(), a = read(), j = read(), b = read();
        link[i + (a ^ 1)*n].push_back(j + b * n);
        link[j + (b ^ 1)*n].push_back(i + a * n);
    }

    for(register int k = 1; k <= 2 * n; k++)
        if(!dfn[k]) tarjan(k);
    for(register int k = 1; k <= n; k++)
        if(col[k] == col[k + n])
        {
            puts("IMPOSSIBLE");
            return 0;
        }
    puts("POSSIBLE");

    for(register int k = 1; k <= n; k++)
        if(col[k] > col[k + n]) printf("1 ");
        else printf("0 ");

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$~\$


结语:

$\qquad$ 考 CSP 时的 RP 已经够烂了,省选 RP 总该高一点吧。




前言:

$~\$

$\quad\quad$ 本文是很早以前写的图论知识拓展,不算很难,但也不简单。

$\quad\quad$ 本文原网址: https://xjx885.coding-pages.com/post/ji-chu-tu-lun-zhi-shi-tuo-zhan/ ,这边 Latex 炸了,建议过去看。

$\quad\quad$ 本文建议和 图论复习笔记 一起食用。


$~\$

正文:

$~\$

$\quad Section\ 1:$ 最短路算法的简单拓展

$\quad\quad$ 本节主要介绍最短路基础算法的一些简单拓展。

$~\$

$\quad\quad$ $1-1:$ $Floyd$的拓展应用

$\quad\quad$ $Floyd$ 是最基础的最短路算法之一,其最基本应用,便是求$n$个点($n$一般不大于$500$)两两之间的最短路,本质为一种枚举中转节点的DP,简单易上手,常数小,复杂度$O(n^3)$,虽然跑$n$遍SPFA或者$n$遍$Dijkstra$可以获得更优的理论复杂度,但是实际复杂度与它差不了很多。故$Floyd$成为处理一些问题的首选算法。

$\quad\quad$ $Floyd$除了求最短路,也可以求有向图的传递闭包(判断两个点是否连通),方法很简单,只要将Floyd中的
$$dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j])$$

改为

$$dis[i][j] = dis[i][j]\ \ | \ \ (dis[i][k] \ \ \&\&\ \ dis[k][j])$$

即可(后面的$dis[i][j]$为一个$bool$数组,表示$i,j$两点是否连通),该方法的证明与$Floyd$求最短路的证明相同,这里略去。

$~\$

  • 解析:板子,解析略。

  • 代码:

#include <bits/stdc++.h>

using namespace std;

int n, m;

//两个map,分别为名字到编号的映射及其反向映射
map <string , int > number;
map <int , string > name;

//判断两个人之间是否可达
bool connect[30][30];

//判断最后输出时有没有输出过
bool used[30];

int tot;
int get_num(string x)
{
    if(number.find(x) != number.end())
        return number[x];
    else
    {
        name[++tot] = x;
        return number[x] = tot;
    }
}

int main()
{
    ios::sync_with_stdio(false);

    int opt = 0;

    while(cin >> n >> m)
    {
        if(n == 0) break;

        number.clear(), name.clear();
        memset(used, 0, sizeof(used));
        memset(connect, false, sizeof(connect));

        tot = 0;
        for(int k = 1; k <= m; k++)
        {
            string a, b;
            cin >> a >> b;

            //连初始边
            int num1 = get_num(a), num2 = get_num(b);
            connect[num1][num2] = true;
        }

        //Floyd过程
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    if(k != i && k != j && i != j)
                        connect[i][j] = connect[i][j] || (connect[i][k] && connect[k][j]);

        cout << "Calling circles for data set " << ++opt << ':' << endl ;
        //输出时只输出还没有经过的点(不在已有电话圈内的点)
        for(int i = 1; i <= n; i++)
            if(!used[i])
            {
                cout << name[i], used[i] = 1;
                for(int j = 1; j <= n; j++)
                    if(connect[i][j] && connect[j][i] && !used[j])
                        cout << ", " << name[j], used[j] = 1;
                cout << endl;
            }
    }

    return 0;
}

$~\$

$\quad\quad$ $Floyd$ 算法还可以用来求正权无向图最小环。

$\quad\quad$ 我们从 $Floyd$ 的本质入手,它最外层的循环枚举的是中转节点,当它枚举到 $k$ 时,意味着:我们现在 $f$ 数组中的最短路,是仅经过 $1\ -\ k-1$ 节点中转的最短路。

$\quad\quad$ 我们再分析最小环的性质:如果我们取最小环上 相邻 的三点 $i,k,j$,则这个最小环由 $(i,k)$,$(k,j)$ 两条边以及不过 $k$ 的 $i,j$ 两点间的路径组成。

$\quad\quad$ 显然,我们 $Floyd$ 刚跑到 $k$ 时,$f$ 中存储的最短路都是不过 $k$ 中转的。所以我们可以枚举 $i,j$ 用 $c(i,k)+c(k,j)+f(i,j)$ 更新答案($c(i,j)$ 表示原图中 $(i,j)$ 边的长度)。

$\quad\quad$ 但这样还有一个问题:如果 $i,j$ 之间不过 $k$ 的那条路径,要经过序号在 $k$ 以后的点中转(比如说 $k’$),那么 $f(i,j)$ 不就不是最短路了吗?这个不要紧,因为这种情况只是把答案算大了而已,不影响最终答案,最终答案会在枚举到 $k’$ 的时候取得。

$~\$

  • 代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

inline int read();

int n, m, ans , f[N][N], c[N][N];

signed main()
{
    n = read(), m = read(), ans = 0x3f3f3f3f;
    memset(f, 0x1f, sizeof(f));
    memset(c, 0x1f, sizeof(c));
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read(), w = read();
        f[u][v] = f[v][u] = min(f[u][v], w);
        c[u][v] = c[v][u] = min(c[u][v], w);
    }

    for(register int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(k != i && i != j && k != j)
                    ans = min(ans, c[i][k] + c[k][j] + f[i][j]);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(k != i && i != j && k != j)
                    if(f[i][k] + f[k][j] < f[i][j])
                        f[i][j] = f[i][k] + f[k][j];
    }


    if(ans <= 1e7) printf("%d", ans);
    else puts("No solution.");

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\$

$\quad\quad$ 除此之外,关于$Floyd$算法的第一层循环(枚举中转点)的顺序也值得探究,它并不是一定要从$1-n$,如果你试着把它改为$n-1$也是没有问题的。事实上,第一层循环枚举节点的顺序是任意可变的。一些题目可以利用这个性质解决。

$~\$

  • 解析:如果不管题面的“未修复完成”这一条件,那么本题便是一道最短路的模板题。我们观察题目条件:村庄是依次修复完毕的,我们不能经过未修复的村庄。或者换一种说法,我们只能通过已修复的村庄中转。“经过某些点中转”正对应着我们Floyd算法的第一层循环。因此,我们可以随着修复的过程,同时进行$Floyd$过程,使得在每一次询问时,我们得到的是通过此时已修复的点中转的最短路,从而在相当于一次$Floyd$的时间中求出答案。具体细节见代码。

  • 代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, m , Q;

//描述每一个村庄的修建时间与村庄编号(改为以1为开始)
//因为题目保证村庄修好的顺序是0->1->2...->n-1 所以这里采用队列
struct node
{
    int num;
    int rebuild_time;

    node (int a, int b)
    {
        num = a, rebuild_time = b;
    }
    node () { }
};
queue <node > vil;

int dis[N][N];//经过已经修好的村庄的最短路

bool re_build[N];//是否已经修好

int main()
{
    memset(dis, 0x3f, sizeof(dis));

    scanf("%d %d", &n, &m);
    for(int k = 1; k <= n; k++)
    {
        int x;
        scanf("%d", &x);

        vil.push(node(k, x));
    }

    for(int k = 1; k <= m; k++)
    {
        int i, j, w;
        scanf("%d %d %d", &i, &j, &w);
        i++, j++;

        dis[i][j] = dis[j][i] = w;
    }

    scanf("%d", &Q);
    for(int q = 1; q <= Q; q++)
    {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        x++, y++;

        //开始修村庄
        while(!vil.empty() && vil.front().rebuild_time <= t)
        {
            int k = vil.front().num;
            vil.pop(), re_build[k] = true;

            //这里就是Floyd去掉最外层循环后的两层循环
            //代表以q.front节点中转带来的更新
            //最外层的枚举k的循环被 时间向前推进而带来的队首的出队 而代替
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    if(i != k && i != j && k != j && dis[i][k] + dis[k][j] < dis[i][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
        }

        if(!re_build[x] || !re_build[y] || dis[x][y] == 0x3f3f3f3f)
            printf("-1\n");
        else
            printf("%d\n", dis[x][y]);
    }

    return 0;
}

$\quad\quad$ $Floyd$的拓展应用自然远不仅此,但是一般来说,这些知识应该是够用了的。

$~\$

$\quad\quad$ $1-2:$ $Dijkstra$的堆优化

$\quad\quad$ 读者大概是知道$Dijkstra$的堆优化的,没有堆优化的$Dijkstra$,就像$Bellman-Ford$算法一般冷门,虽然说我们习惯性说$Dijkstra$堆优化后的复杂度为$O((m+n)logn)$,但是实际上,使用STL中的$priority_queue$跑出来的时间复杂度远不止这个值。理由是堆中存储了大量冗余元素,这些冗余元素虽然会在达到堆顶时因为已经solved而被拿掉,但是会使得堆中操作的复杂度增大,虽然一般来说不会有题目卡这一点,但是我们还是应该知道解决这个问题的方法…

$\quad\quad$ 最简单的方法是更改我们所使用的堆,使用一些高级的堆结构(只要能修改堆中元素就行)。比如说可并堆,基本所有可并堆都可以,包括左偏树,配对堆,迪杰斯特拉堆(真的有人用这玩意吗?)之类的。优化思路很简单,把元素的插入替换成更改元素的值就好,这样堆内的元素就不会超过 $n$ 个了。

$\quad\quad$ 这里放个 平板电视维护堆优化$Dijkstra$的链接(pb_ds 比赛的时候不太敢用,但平常用用还是挺方便的)

$\quad\quad$ 提供两份记录,证明该优化的有效性…

$\quad\quad$ 在均没开包括快读之内的任何优化的情况下,对于洛谷P4779 【模板】单源最短路径(标准版)

优化前总时间1.22s

优化后总时间791ms

  • 解析:最短路板子题,但是可以卡掉没有优化的$Dijkstra$ (本题总时间可以进2000ms)

  • 代码:

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;

template < typename T > inline void read(T &x)
{
#define gcc getchar
    x = 0;
    char ch = gcc();

    for( ; ch < '0' || ch > '9'; ch = gcc());
    for( ; ch >= '0' && ch <= '9'; ch = gcc()) x = (x << 1) + (x << 3) + (ch ^ 48);

    return ;
}

#define L 1e8-100*a
#define mp make_pair

typedef long long LL;
typedef __gnu_pbds::priority_queue < pair<LL, int>, greater< pair<LL, int> >, pairing_heap_tag > heap;

const int N = 1e6 + 3;
const int M = 1e7 + 3;

struct Edge
{
    int to, dis, nxt;
};

Edge E[M];
int cnt, head[N];

inline void addEdge(int u, int v, int d)
{
    E[++cnt].to = v;
    E[cnt].dis = d;
    E[cnt].nxt = head[u];
    head[u] = cnt;
}

int n, m, T, rxa, rxc, rya, ryc, rp, a, b, x, y, z;

LL dis[N];

inline void dijkstra()
{
    memset(dis,0x3f,sizeof(dis)),dis[1] = 0;

    heap q;
    vector < heap::point_iterator > id;
    id.reserve(N),id[1] = q.push(mp(0, 1));

    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();

        for(int i = head[u]; i; i = E[i].nxt)
        {
            int v = E[i].to;

            if(dis[u] + E[i].dis < dis[v])
            {
                dis[v] = dis[u] + E[i].dis;

                if(id[v] != 0) q.modify(id[v], mp(dis[v], v));
                else id[v] = q.push(mp(dis[v], v));
            }
        }
    }
}

int main(void)
{
    read(n), read(m);
    read(T), read(rxa), read(rxc), read(rya), read(ryc), read(rp);

    m -= T;

    for( ; T; --T)
    {
        x = 0, y = 0, z = 0;

        x = ((LL)x * rxa + rxc) % rp;
        y = ((LL)y * rya + ryc) % rp;

        a = min(x % n + 1, y % n + 1);
        b = max(y % n + 1, y % n + 1);

        addEdge(a, b, L);
    }

    for(int i = 1; i <= m; ++i)
    {
        read(x), read(y), read(z);
        addEdge(x, y, z);
    }

    dijkstra();

    printf("%lld", dis[n]);

    return 0;
}

$~\$

$\quad\quad$ $1-3:$ $SPFA$的$SLF$优化

$\quad\quad$ $SPFA$,一向是一个让人纠结的算法…你说不用吧,它平均跑的飞快…你说用吧,又会被卡… 这里介绍$SPFA$最简单而有效的优化,可以让你的$SPFA$稍微快一些(当然,该被卡还是被卡)

$\quad\quad$ $SLF$优化的全称是$Small\ Label\ First $ 优化, 正如其名,该优化的原理是,尽量让使用的队列”像”一个前小后大的单调队列,这样更有拓展价值的点在队列头部,使得操作总时间变短。

$\quad\quad$ 具体操作是,把$SPFA$所使用的队列改为双端队列,放入元素的时候,如果该元素小于队首元素,那么放在队首,否则放在队尾。下面是插入时的代码。

if(q.empty() || dis[to] < dis[q.front()])
    q.push_front(to);
else
    q.push_back(to);

$\quad\quad$ 例题就略去了,毕竟这个优化太简单了…

$\quad\quad$ 虽然$SPFA$还有其它优化,但是都不稳定,代码也有些复杂,不像$SLF$优化一样,随手一加就好,所以略去不讲。

$~\$

$~\$

$\quad Section\ 2:$ 生成树相关

$\quad\quad$ 本节主要介绍一些与$Kruskal $有关的瓶颈问题。

$~\$

$\quad\quad$ $2-1:$ 最小瓶颈路和最小瓶颈生成树

$\quad\quad$ 如果让你在一个图上,从 $a$ 点到 $b$ 点的路径中,找一条路径,使路径上的最长边边权尽量小,你怎么做?

$\quad\quad$ 方法理所当然是很多的,比如说二分,比如说BFS,但是这里介绍一种基于最小瓶颈生成树的方法…刚刚的问题实质上是询问一张图上,从 $a$ 到 $b$ 的最小瓶颈路(其定义就是两点间最长边最短的路径)。而什么是最小瓶颈生成树呢?就是在让树上的最长边尽量短之后得到的生成树,而我们很容易推得,$a->b$的最小瓶颈路一定至少有一条在最小瓶颈生成树上。

$\quad\quad$ 为什么?我们假设$a->b$的最小瓶颈路不在最小瓶颈生成树上。令$a->b$最小瓶颈路上最长边的权值为$x$,在最小瓶颈生成树上,$a->b$的权值为$y$,那么有$x[HTML_REMOVED]y$,那么显然这条“最小瓶颈路”不是真正的最小瓶颈路,如果$x=y$,那么最小瓶颈生成树上的那条路就也是一条$a->b$的最小瓶颈路)。我们不妨把$x$边和最小瓶颈生成树上的边,放在一起,我们发现,它们形成了一个环(显然,给一棵树多加条边,自然成环)。$x$是一定在环上的,我们讨论$y$,假设$y$在环上,那么去掉$y$,选择$x$显然可以让我们的最小瓶颈生成树更优,此时我们的最小瓶颈生成树并非真正的“最小”,与条件矛盾。假设$y$不在环上,那么我们可以不选$y$,沿着最小瓶颈路上的边和最小瓶颈生成树上除$y$外的其他边,构建一棵生成树(一定可以构建出来,画画图就知道了)此时,最小瓶颈生成树也不是真正的“最小”,假设不成立。

$\quad\quad$ 因此,通过反证法,我们可以证明,$a->b$的最小瓶颈路一定至少有一条在最小瓶颈生成树上。

$\quad\quad$ 那么如何求最小瓶颈生成树呢?很简单,无向图的最小生成树就是它的一种最小瓶颈生成树。观察我们$Kruskal $算法的过程,我们从小到大能加边就加边,所以我们加入到生成树中的边都是尽量小的,符合最小瓶颈树额要求。因此,我们可以把求最小瓶颈路的过程转化为求最小生成树上两点路径上边权的最大值的过程。这个最大值可以建树后使用倍增解决。

$\quad\quad$ 该做法可以做到$O(nlogn)$预处理,$O(logn)$查询,从而解决多次询问最小瓶颈路的问题。

$~\$

  • 代码:
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, S, Q;

struct node
{
    int a, b, c;

    node (int aa, int bb, int cc)
    {
        a = aa, b = bb, c = cc;
    }
    node () { }

    bool operator < (const node & other ) const
    {
        return c < other.c;
    }
};
vector <node > Link;

int fa[N],deep[N];

//倍增数组:倍增父亲和倍增最大值 
int f[N][10] , g[N][10];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct node0
{
    int to, len;

    node0(int a, int b)
    {
        to = a, len = b;
    }
    node0() { }
};

//跑出来的最小生成树一定是最小瓶颈树 
vector <node0 > link[N];

void Kruskal()
{
    int tot = 0;

    sort(Link.begin(), Link.end());

    for(int k = 0; k < (int )Link.size(); k++)
    {
        if(tot == n - 1)
            break;

        int a = Link[k].a, b = Link[k].b, c = Link[k].c;

        if(find(a) != find(b))
        {
            link[fa[a]].push_back(node0(fa[b], c));
            link[fa[b]].push_back(node0(fa[a], c));

            fa[fa[a]] = fa[b], tot++;
        }
    }
}

//倍增预处理 
void dfs(int wz, int fa)
{
    deep[wz] = deep[fa] + 1, f[wz][0] = fa ;
    for(int k = 1; k < 10; k++)
        f[wz][k] = f[f[wz][k - 1]][k - 1];
    for(int k = 1; k < 10; k++)
        g[wz][k] = max(g[wz][k - 1], g[f[wz][k - 1]][k - 1]);

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int to = link[wz][k].to;

        if(to == fa) continue;

        g[to][0] = link[wz][k].len;

        dfs(to, wz);
    }
}

//倍增求路径上边权的最大值 
int LCA(int a, int b)
{
    int ans = -1;

    if(deep[a] < deep[b])
        swap(a, b);

    for(int k = 9; k >= 0; k--)
        if(deep[a] - (1 << k) >= deep[b])
            ans = max(ans, g[a][k]), a = f[a][k] ;

    if(a == b)
        return ans;

    for(int k = 9; k >= 0; k--)
        if(f[a][k] != f[b][k])
            ans = max(ans, g[a][k]), ans = max(ans, g[b][k]), a = f[a][k], b = f[b][k];

    return max(max(ans, g[a][0]), g[b][0]);
}

int main()
{
    int opt = 0;

    while(scanf("%d %d %d", &n, &S, &Q))
    {
        if(n == 0) break;

        //初始化
        memset(deep, 0, sizeof(deep));
        memset(link, 0, sizeof(link));
        Link.clear();

        //坑爹的换行
        if(opt++ != 0)
            printf("\n");

        printf("Case #%d\n", opt);

        //并查集初始化
        for(int k = 1; k <= n ; k++)
            fa[k] = k;

        for(int k = 1; k <= S; k++)
        {
            int c1, c2, d;
            scanf("%d %d %d", &c1, &c2, &d);

            Link.push_back(node(c1, c2, d));
        }

        //生成树过程 
        Kruskal();

        for(int k = 1; k <= n; k++)
            if(!deep[k])
                dfs(find(k), 0);

        for(int k = 1; k <= Q; k++)
        {
            int c1, c2;
            scanf("%d %d", &c1, &c2);

            if(find(c1) == find(c2))
                printf("%d\n", LCA(c1, c2));
            else
                printf("no path\n");
        }
    }

    return 0;
}

$~\$

$\quad\quad$ $2-2:$ $Kruskal$重构树

$\quad\quad$ 如果你把$2-1$看懂了,例题A了,那么这一节也不难看懂。$Kruskal$重构树也是解决与最小瓶颈路有关的问题的,它比刚刚讲的最小瓶颈生成树要更加灵活,也更加好写。

$\quad\quad$ 如何构造一棵$Kruskal$重构树?很简单,先跑$Kruskal$算法,如果向生成树中加入一条边 $E$,就新建一个节点 $P$,点权为这条边的边权,然后从这个点,向 $E$ 连接的两个连通块的顶($fa$)节点连边,并将之作为两连通块的 $fa$。跑完$Kruskal$后,$Kruskal$重构树就建立好了。

$\quad\quad$ 它有什么性质?首先,它是棵树(废话),它的叶子节点(即原图中的节点)没有权值,对于非叶节点,它的权值一定小于它父亲的权值。对于任意两个叶子节点,它们LCA的权值一定是它们在原图中最小瓶颈路上最大边的权值。

$\quad\quad$ 可以看出,$Kruskal$ 重构树其实就是上面的最小瓶颈树的等价变形,把原本瓶颈树上不易维护和查找的信息,转化成了重构树上易操作的信息。有点类似做物理电路题时用的等效电路法,有的问题放在原电路上根本看不出答案,但构建出等效电路后答案就清晰多了。

$\quad\quad$ 更具体证明和推理,这里就略去了,放一个讲$Kruskal$重构树的日报的链接

$\quad\quad$ 仍然以上面那题作为例题,这里就不多放图了,解析和代码可以看我写的一篇题解

$~\$

  • 解析:本题可以用$Kruskal$ 重构树解决,我们先建立根节点最小的$Kruskal$ 重构树(换句话说就是,跑$Kruskal$ 时用按海拔从大到小对边进行排序,选择海拔最高的几条边组成最大生成树)。对于每一次询问,从当前节点向上找一个海拔最低但高于当前水线的点,以这个点为根的子树中的所有叶子节点就是可以从起点开车去的点。再从这些点中选择一个离1最近的点,开车过去,然后步行至1节点。本题就解决了。

$~\$

$~\$

$\quad$ $Section\ 3:$ 拓扑的综合应用

$\quad\quad$ 本节主要介绍拓扑排序的一些组合拓展。

$~\$

$\quad\quad$ $3-1:$ $tarjan$缩点,拓扑的综合应用

$\quad\quad$ 拓扑排序本质上就是 DAG 上的递推序,我们可以在它的基础上 DP 解决很多图论问题,但如果题目给出的图不是 DAG 呢?那就只有先缩点再处理了。

  • 解析:这样的题目的一般思路是:先思考怎么把一个强连通缩成一个点,再思考图变为DAG后,怎么跑拓扑排序,最后合起来,一遍缩点,一遍拓扑就可以了。对于本题,我们发现,对于一个强连通分量,它的任何两个个子节点都互相可达,所以可以把它看作一个权值为其内节点个数的“大点”。而对于一张DAG,如果存在一条边由 $u$ 指向 $v$,那么到 $v$ 结束的节点集的节点数应对 到$u$结束的联通的节点的权值和与$v$的权值之和 取$max$($u$,$v$可以形成节点集)。因此,先缩点,再拓扑,就可以得到本题的解。

  • 代码:

#include <bits/stdc++.h>

const int N = 1010;
const int M = 50010;

int tot, n, m , color ;

int dfn[N], low[N] , col_p[N];
int ind[N], max[N] , d[N];

bool in[N];

std::stack <int > s;
std::vector <int > link[N];
std::vector <int > new_link[N];

void init()
{
    //数据清空
    memset(link, 0, sizeof(link));
    memset(new_link, 0, sizeof(new_link));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(max, 0, sizeof(max));
    memset(d, 0, sizeof(d));
    tot = 0 , color = 0;

    //读入
    scanf("%d %d", &n, &m);
    for(int k = 1; k <= m; k++)
    {
        int u, v;
        scanf("%d %d", &u, &v);

        link[u].push_back(v);
    }
}

//tarjan求强联通分量
void tarjan(int wz)
{
    dfn[wz] = low[wz] = ++tot;
    in[wz] = true, s.push(wz);

    for(int k = 0; k < (int )link[wz].size() ; k++)
    {
        int to = link[wz][k];

        if(!dfn[to])
            tarjan(to), low[wz] = std::min(low[wz], low[to]);
        else if(in[to])
            low[wz] = std::min(low[wz], low[to]);
    }

    if(dfn[wz] == low[wz])
    {
        color++;

        while(s.top() != wz)
        {
            in[s.top() ] = false;
            col_p[s.top() ] = color;

            s.pop(), d[color]++;
        }

        in[wz] = false;
        col_p[wz] = color;

        s.pop() , d[color]++;
    }
}

//缩点,重构图
void build_link()
{
    for(int k = 1; k <= n; k++)
        for(int i = 0; i < (int )link[k].size() ; i++)
        {
            int to = link[k][i];

            if(col_p[to] != col_p[k])
                new_link[col_p[k]].push_back(col_p[to]), ind[col_p[to]]++;
        }
}

//拓扑排序 d[i]代表i的点权,max[i]代表到以i结束的最大节点集内的所有点点权和的最大值 
void topo()
{
    int answ = 0;

    std::queue <int > q;

    for(int k = 1; k <= color; k++)
        if(!ind[k])
            q.push(k), max[k] = d[k];

    while(!q.empty() )
    {
        int wz = q.front();
        q.pop();

        for(int k = 0; k < (int )new_link[wz].size() ; k++)
        {
            int to = new_link[wz][k];

            max[to] = std::max(max[to], max[wz] + d[to]);

            if(--ind[to] == 0)
                q.push(to);
        }
    }

    for(int k = 1; k <= color; k++)
        answ = std::max(answ, max[k]);

    printf("%d\n", answ);
}

void work()
{
    for(int k = 1; k <= n; k++)
        if(!dfn[k])
            tarjan(k);

    build_link();

    topo();
}

int main()
{
    int opt;
    scanf("%d", &opt);

    while(opt--)
    {
        init();

        work();
    }

    return 0;
}

$\quad\quad$ 提示:按照拓扑+强连通的一般思路,我们可以把互相都可以到达的点缩成一个点,然后点权就是该连通块里的点的个数,至于各个连通块之间的转移,与上题几乎一样。本题与上题唯一的不同就在于建边不好建,数据规模太大…不过我们可以只挑有用的点(转送门)建边,如果一个传送门可以到另一个传送门,那么我们建一条边。然而就算这样,边数任然太多。我们考虑优化..一个非常显然的优化是:对于一排的“横天门”,直接在最开始的时候就缩成一个点,对于一列的纵寰门”,同样缩成一个点。这样处理后,边数就会大大减少。

$~\$

$\quad\quad$ $3-2:$ 最短路,拓扑的综合应用

$\quad\quad$ 让一个有向图变为DAG,并不只有$tarjan$缩点的方法。我们注意到:最短路网一定是一个DAG,所以,当题目的边依赖于最短路时,可以先构造最短路网,然后再跑拓扑排序。注意:不仅最短路网是一个DAG,多个不同起点的最短路网的交或并也一定是DAG(可以看做建立了一个超级源,沿着它跑最短路网)。

$\quad\quad$ 具体操作上,如果说题目要求从 $S$ 出发,到达其他点时必须走最短路,那么我们可以x先跑出 $S$ 出发的最短路,再判断各条边是否在最短路网上。如何判断一条边在不在最短路网上?若从$u$出发有一条边指向$v$,边权为$len$,且$dis(u)+len=dis(v)$,那么该边就在最短路网上。

  • 解析:观察题目,我们注意到:两人比起“在一起的时间最长”,更期望“走的路程最短”。换句话说,最短路是第一关键字,是在走最短路的前提下重叠最长。所以我们可以先跑出最短路网,在最短路网之外的其它边是完全没有意义的(因为两人走最短路不会经过那些边)。然后,我们所求的就是最短路网交集中的最长链,把最短路网中的分别标记一下,如果一条边同时被两个最短路网所标记,那么它就在最短路网的交集中,我们把交集中的点拿出来再建图,很显然,建出来的图也是DAG,然后跑一下拓扑,求出最长链就可以了。本题有些坑的是:两人路径反向相交(相遇)也算走在一起。

  • 代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 1510;

int n, m;
int X1, Y1, X2, Y2;

//两人的正反向最短路,共四次最短路 
int dis1[N], dis2[N];
int f_dis1[N], f_dis2[N];

struct node
{
    int to, len;
    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};
vector <node > link[N];

bool in[N];
queue <int > q;

//四次最短路(我当初的马蜂诶...) 
void SPFA()
{
    memset(dis1, 0x3f, sizeof(dis1));
    dis1[X1] = 0, in[X1] = true, q.push(X1);

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = false;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis1[wz] + len < dis1[to])
            {
                dis1[to] = dis1[wz] + len;

                if(!in[to])
                    in[to] = true, q.push(to);
            }
        }
    }

    memset(dis2, 0x3f, sizeof(dis2));
    dis2[X2] = 0, in[X2] = true, q.push(X2);

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = false;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis2[wz] + len < dis2[to])
            {
                dis2[to] = dis2[wz] + len;

                if(!in[to])
                    in[to] = true, q.push(to);
            }
        }
    }

    memset(f_dis1, 0x3f, sizeof(f_dis1));
    f_dis1[Y1] = 0, in[Y1] = true, q.push(Y1);

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = false;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(f_dis1[wz] + len < f_dis1[to])
            {
                f_dis1[to] = f_dis1[wz] + len;

                if(!in[to])
                    in[to] = true, q.push(to);
            }
        }
    }

    memset(f_dis2, 0x3f, sizeof(f_dis2));
    f_dis2[Y2] = 0, in[Y2] = true, q.push(Y2);

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = false;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(f_dis2[wz] + len < f_dis2[to])
            {
                f_dis2[to] = f_dis2[wz] + len;

                if(!in[to])
                    in[to] = true, q.push(to);
            }
        }
    }
}

//最短路网(重构图)中的边 
vector <node > new_link[N];
vector <node > new_link2[N];
int ind[N];
int ind2[N];

//bitset大法好 
bitset <N > visit[N];
bitset <N > visit2[N];

//重构图过程 
void creat()
{
    SPFA();
    for(int k = 1; k <= n; k++)
        for(int i = 0; i < (int )link[k].size(); i++)
        {
            int to = link[k][i].to;
            int len = link[k][i].len;

            if(dis1[k] + f_dis1[to] + len == dis1[Y1])
                new_link[k].push_back(node(to, len)), ind[to]++, new_link2[k].push_back(node(to, len)), ind2[to]++;
            if(dis2[k] + f_dis2[to] + len == dis2[Y2])
                new_link[k].push_back(node(to, len)), ind[to]++, new_link2[to].push_back(node(k, len)), ind2[k]++;
        }
};

//拓扑排序数组 
int f[N];
int f2[N];

int maxn;

//两次拓扑,分别为正向相交的最长链和反向相交的最长链 
void topu1()
{
    memset(f, 0xef, sizeof(f));

    for(int k = 1; k <= n; k++)
        if(ind[k] == 0)
            q.push(k), f[k] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop();

        for(int k = 0; k < (int )new_link[wz].size(); k++)
        {
            int to = new_link[wz][k].to;
            int len = new_link[wz][k].len;

            f[to] = max(f[to], f[wz]);

            if(visit[wz][to] || visit[to][wz])
                f[to] = max(f[to], f[wz] + len), maxn = max(maxn, f[to]);
            else
                visit[wz][to] = true;

            if(--ind[to] == 0)
                q.push(to);
        }
    }
}
void topu2()
{
    memset(f2, 0xef, sizeof(f2));

    for(int k = 1; k <= n; k++)
        if(ind2[k] == 0)
            q.push(k), f2[k] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop();

        for(int k = 0; k < (int )new_link2[wz].size(); k++)
        {
            int to = new_link2[wz][k].to;
            int len = new_link2[wz][k].len;

            f2[to] = max(f2[to], f2[wz]);

            if(visit2[wz][to] || visit2[to][wz])
                f2[to] = max(f2[to], f2[wz] + len), maxn = max(maxn, f2[to]);
            else
                visit2[wz][to] = true;

            if(--ind2[to] == 0)
                q.push(to);
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);

    for(int k = 1; k <= m; k++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        link[a].push_back(node(b, c));
        link[b].push_back(node(a, c));
    }

    creat();

    topu1();
    topu2();

    printf("%d", maxn);

    return 0;
}

  • 总结一下,对于拓扑排序可以解决的题目,我们的解法是把图变为可以跑拓扑的DAG,然后跑拓扑求解。

$~\$

$~\$

$\quad$ $Section\ 4:$ 图论上的状压DP

$\quad\quad$ 本节主要介绍图论(不包括树)中出现比较多的DP:状压DP。

$~\$

$\quad\quad$ 状压DP主要适用于一些关键点比较少的图论问题,同时题目一般对这几个关键点有特殊要求,比如说:只能经过一次,必须都经过等等。因此,图论上跑的状压DP都比较容易看出来。它状态的表示,一般都包括两种信息:第一种是我走过了哪些关键点,这个信息一般状压一维来表示;第二种是我现在在哪,这种信息可以直接使用大小为$n$的一维维护,也可以根据题目特点,设立多维进行维护。而状压DP上的转移,无非就是关键点与关键点之间的转移,一般来说可以直接根据最短路转移,而以每个关键点为起点的最短路可以在之前预处理出来。

  • 解析:本题状压的思路非常明显:$n$的个数比较小。所以我们可以设置状态为$f(i)(j)$表示二进制状压后,经过了 $i$ 集合中的节点,到了 $j$ 号点。转移就是去一个没到过的城市,初态末态都很简单,随便就可以切掉。

  • 代码:

#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>

const int N = 19;
const int MAXN = (1 << 19);

int n, m;

//f[i][j]表示走过了j(状压数组),到了i 
int f[N][MAXN];

struct node
{
    int to, len;

    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};
std::vector <node > link[N];

void init()
{
    scanf("%d %d", &n, &m);
    for(int k = 1; k <= m; k++)
    {
        int s, d, l;
        scanf("%d %d %d", &s, &d, &l);

        d++, s++;
        link[d].push_back(node(s, l));
    }
}

//倒推的记忆化搜索 
int dfs(int wz, int visit)
{
    if(f[wz][visit] != -44444444)
        return f[wz][visit];

    if(!visit)
        return -44444444;

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int to = link[wz][k].to;
        int len = link[wz][k].len;

        if(visit & (1 << (to - 1)))
            f[wz][visit] = std::max(f[wz][visit], dfs(to, visit ^ (1 << (wz - 1))) + len);
    }

    return f[wz][visit];
}

void work()
{
    //初始化 
    for(int k = 0; k <= n; k++)
        for(int i = 0; i < MAXN; i++)
            f[k][i] = -44444444;
    f[1][1] = 0;

    int answ = -44444444;

    //记忆化搜索(我习惯倒着推,不过本题正着推似乎更容易 ) 
    for(int k = 1; k < MAXN; k++)
        answ = std::max(answ, dfs(n, k | (1 << (n - 1))));

    printf("%d\n", answ);
}

int main()
{
    init();

    work();

    return 0;
}

$~\$

  • 解析:本题比上一题复杂一些,从必须经过节点变成了必须经过边。我们发现,本题要经过的边数仅仅只有12条,似乎可以使用状压DP,设$f(i)(j)$为走过二进制状压后集合为$i$的桥,停在$j$点时的最短路径。转移很明显是走某一座没走过的桥,直接走最短路一定最优。不过,因为本题点太多,$2^{12}*50000$ 会爆空间,所以我们需要把图改造一下。我们注意到,本题中供给停留的点,无非就是起点和一座桥链接的两个点而已。我们大可以通过最短路,把图重构为这最多25个点的图。然后跑刚刚的状压DP就好。

  • 代码(这题难度还是有的,我在大半年前的比赛时居然半小时就切了,真是不可思议,20/6/17):

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 50010;

int INF;
int n, m, K;

struct node
{
    int to, len;

    node (int a, int b)
    {
        to = a, len = b;
    }
    node () { }
};

vector <node > link[N];

//标号为i的桥的两个端点的编号和桥长 
//桥的两个端点本质上不分左右,下文的左右都是抽象出来的 
int wz[14][2], Len[14];

//以标号为i的桥的左/右端点开始的最短路(起点设置为了0号桥的左右端点) 
int dis[N][14][2];

queue <int > q;
bool in[N];

//SPFA ori和aorb其实只是表示当前跑SPFA的是哪个点 
void SPFA(int S, int ori, int aorb)
{
    memset(in, false, sizeof(in));

    dis[S][ori][aorb] = 0;
    q.push(S), in[S] = true;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = false;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int to = link[wz][k].to;
            int len = link[wz][k].len;

            if(dis[wz][ori][aorb] + len < dis[to][ori][aorb])
            {
                dis[to][ori][aorb] = dis[wz][ori][aorb] + len;

                if(!in[to])
                    q.push(to);
            }
        }
    }

}

//状压数组f[k][i][j]表示走过了k(状压数组)桥,到达了第i座桥的左\右端点
//到达其他的点是没有意义的,而在点与点之间行走,最优的一定是最短路 
int f[1 << 13][14][2];

//dfs的三个参数对应k,i,j 
int dfs(int get, int now, int aorb)
{
    //如果桥走完了,那么回到起点 
    if(get == (1 << K) - 1)
        return dis[1][now][aorb];

    //如果状态出现过了,直接返回 
    if(f[get][now][aorb] != INF)
        return f[get][now][aorb];

    //选择一座没有走过的桥经过它
    //具体的操作是:通过最短路走到它的左端点
    //再走过桥走到它的右端点,这样就走过了一座桥
    //或者走到右端点再过桥,是一样的    
    for(int k = 0; k < K; k++)
        if((get & (1 << k)) == 0)
        {
            //最短路跑到右端点,过桥 
            if(dfs(get | (1 << k), k + 1, 0) != INF)
                f[get][now][aorb] = min(f[get][now][aorb], dfs(get | (1 << k), k + 1, 0) + dis[wz[k + 1][1]][now][aorb] + Len[k + 1]);

            //最短路跑到左端点,过桥 
            if(dfs(get | (1 << k), k + 1, 1) != INF)
                f[get][now][aorb] = min(f[get][now][aorb], dfs(get | (1 << k), k + 1, 1) + dis[wz[k + 1][0]][now][aorb] + Len[k + 1]);
        }

    return f[get][now][aorb];
}

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &K);

    //读入 
    wz[0][0] = wz[0][1] = 1;
    for(int k = 1; k <= K; k++)
    {
        int u, v, len;
        scanf("%lld %lld %lld", &u, &v, &len);
        wz[k][0] = u, wz[k][1] = v, Len[k] = len;

        link[u].push_back(node(v, len));
        link[v].push_back(node(u, len));
    }
    for(int k = K + 1; k <= m; k++)
    {
        int u, v, len;
        scanf("%lld %lld %lld", &u, &v, &len);

        link[u].push_back(node(v, len));
        link[v].push_back(node(u, len));
    }

    //以每一个关键点(起点或者桥的左右两个节点)为起点,预处理出最短路 
    memset(dis, 0x3f, sizeof(dis));

    SPFA(1, 0, 0);
    for(int k = 1; k <= K; k++)
        SPFA(wz[k][0], k, 0), SPFA(wz[k][1], k, 1);

    memset(f, 0x3f, sizeof(f));
    INF = f[0][0][0];

    printf("%lld", dfs(0, 0, 0));

    return 0;
}

$~\$

$~\$

$\quad$ $Section\ 5:$ 最短路算法拓展

$\quad\quad$ 本节主要介绍一些略微复杂的最短路。

$~\$

$\quad\quad$ $5-1:$ 分层图

$\quad\quad$ 最短路的题目,大多都不会直接给你一张图,你跑一遍,答案就出来了。你需要找到题目中的一些特性,构造图。而构造图的一种很常用的方法就是分层。

$\quad\quad$ 你是否遇到过这样的题目:给定一张图,让你选定$K$条边,使其边权变为零,然后跑最短路,使得最后起点到终点的最短路最小(如果你没遇到过,那么戳进去吧)。如何解决在这种问题?

$\quad\quad$ 一般来说,这种问题$K$都会比较小,所以我们可以强制拆点,把一个点拆成($K+1$)个点,每建立$K+1$层图(可以理解为把原图复制$K+1$份)。我们可以把这些图依次从$0-K$编层,第$i$层表示已经选了$i$条边之后的图。很显然,对于本题,选边对原图中连边的方式没有影响,所以我们每一层内的边,就按原图中的边连。而对于层与层之间,我们让第$i$层连边到第$i+1$层。具体操作是:若原图中有一条$u$到$v$的边,那么就从$i$层的$u$连边到第$i+1$的$v$,边权为0,这代表我们花费一个次数,把 $(u,v)$ 的边权变为 $0$。然后从第零层的起点跑最短路到第$K$层的终点就好了。

$\quad\quad$ 为什么可以这么做?因为如果走一条边权为0的边,就会从$i$层走到$i+1$层,所以当走到第$K$层时,就一定把$K$条边变成了0权。

$~\$

$~\$

$\quad\quad$ $5-2:$ 隐式图

$\quad\quad$ 最短路算法并是只能在给出的图上运用,一些题目虽然没有给出点与边,但是却可以抽象出“点”和“边”,用隐式图最短路解决。

  • 解析:乍看上去,本题是一道搜索题(确实可以搜索),但是可以使用最短路解决。我们把三个杯子的水量$(a , b, c)$抽象为点,把倒水的步骤抽象成边。然后可以直接跑最短路解决。

  • 代码:过 略去

$~\$

  • 解析:本题稍微有些麻烦。拿到本题时,第一反应大概是搜索,看看数据规模,似乎可以记忆化。然而,我们发现,从某些状态搜索下去有可能重新达到这个状态。这导致我们的记搜会陷入无限递归。因此,我们无法用记搜做这道题。(根本原因是这图不是个 DAG)但是,这题可以用最短路解决:我们可以使用二进制表示每时每刻的状态,作为点,把装补丁作为边,权值就是补丁的消耗。在本题中,因为有‘0’的存在,所以把边建出来既慢又麻烦,因此,对于每个点,我们只需要扫描每一条边(补丁),看看能否装上就好了。

  • 代码:

#include <bits/stdc++.h>

using namespace std;

int n, m;

//打补丁前的状态
char ch[110][22];

//打后的状态
char to[110][22];

//每个补丁的代价
int cost[110];

queue <int > q;
bool in[10010000];
int dis[10010000];

//判断能否打该补丁
bool can_add(int wz, int key)
{
    for(int k = 1; k <= n; k++)
        if(ch[wz][k] == '-')
        {
            if(!(key & (1 << (k - 1))))
                return false;
        }
        else if(ch[wz][k] == '+' && (key & (1 << (k - 1))))
            return false;

    return true;
}

//打了该补丁后会变成啥样
int get_to(int wz, int key)
{
    int ret = 0;

    for(int k = 1; k <= n; k++)
        if(to[wz][k] == '0')
            ret += (key & (1 << (k - 1)));
        else if(to[wz][k] == '-')
            ret += (1 << (k - 1));

    return ret;
}

void SPFA()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0, q.push(0), in[0] = true;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop();
        in[wz] = false;

        //直接搜所有补丁,不需要建边
        for(int k = 1; k <= m; k++)
            if(can_add(k, wz))
            {
                int to = get_to(k, wz);

                if(dis[wz] + cost[k] < dis[to])
                {
                    dis[to] = dis[wz] + cost[k];

                    if(!in[to])
                        q.push(to), in[to] = true;
                }
            }
    }

    int end0 = (1 << (n)) - 1;

    if(dis[end0] == 0x3f3f3f3f)
        printf("Bugs cannot be fixed.\n\n");
    else
        printf("Fastest sequence takes %d seconds.\n\n", dis[end0]);
}

int main()
{
    int opt = 0;

    while(scanf("%d %d", &n, &m))
    {
        if(n == 0) break;

        printf("Product %d\n", ++opt);

        for(int k = 1; k <= m; k++)
            scanf("%d %s %s", &cost[k], &ch[k][1], &to[k][1]);

        SPFA();
    }

    return 0;
}

$~\$


结语:

$\quad\quad$ (20/6/17) 想当年,我图论模板闭眼敲,紫题随便切.....现在连模板都忘了,还要考以前的笔记复习......Orz…




前言:

$\quad\quad$ 最近准备省选,把以前的笔记抽出来翻了翻,找到了不少 BUG…于是更新了一下。

$\quad\quad$ $\LaTeX$ 日常炸,建议 Goto 原网址 https://xjx885.coding-pages.com/post/splay-xue-xi-bi-ji/

$\quad\quad$ Update(20/06/15):修复了细节问题(包括但不限于 $\LaTeX$ 和图片和大部分表达)。


$~\$

正文:

$\quad\quad$ 二叉查找树(BST): 一种二叉的,用于查找信息的,树形数据结构。

$\quad\quad$ 具体而言:BST 是一种二叉树,设其上某一节点的值为 $x$,则该节点左子树中的所有点权值都小于 $x$,右子树中所有节点都大于 $x$ (递归定义)。

$\quad\quad$ 为什么叫它查找树呢?因为 BST 支持对树中的 $\operatorname{Kth}$(第 K 大的数是多少) 和某一个值在树中的 $\operatorname{Rank}$(某个数是第几大) 的查询(我一直都不太很分得清 $\operatorname{Kth}$ 和 $\operatorname{Rank}$ ,下面可能会有地方把它们弄混)。

$\quad\quad$ 实现方式是:维护一个 $size$ 数组,记录每个节点的子树大小,查询时,从根节点开始,比较当前 $size$ 与给出信息的大小,然后逐层递归。

$\quad\quad$ 举个例子:当我们查询 $x$ 在 BST 中的排名时,我们先比较它与根节点 $y$ 的大小,如果 $x[HTML_REMOVED]y$ 那么 $x$ 在 $y$ 右儿子对应子树中,此时左儿子对应子树中的节点和根节点一定小于 $x$,我们可以把答案加上 $size(lson(y))+1$。这层处理完后,递归进下一层即可。

$\quad\quad$ 代码这里就不放了,后面和 $Splay$ 的其它函数一起放。

$\quad\quad$ BST 复杂度看起来很优,是 $O(logn)$ 的,但实际效果不好,理由很简单:同一棵二叉查找树有很多不同的形态。

$\quad\quad$ 比如说由1 2 3 4 5构成的二叉查找树…可以是这样的:

$\quad\quad$ 也可以是这样的:

$\quad\quad$ 为什么多形态效果不好呢?因为这意味着出题人可以简单地构造一条链把你卡到 $O(n)$。

$\quad\quad$ 你可能会说: Q:哎呀,那不简单,我们随机打乱一下不就好了吗?

$\quad\quad$ A:那要是出题人要你支持插入操作,插着插着就成链了呢?

$\quad\quad$ Q:Emm…那我们每次操作的时候都打乱一下?

$\quad\quad$ A:每次操作都打乱整棵树,那复杂度得多大啊?

$\quad\quad$ Q:那我们能不能在每次操作时,进行尽量少的打乱操作,却使得整棵树保持 “平衡” 呢?

$\quad\quad$ 这篇文章的主角,就是这样一种特殊的,不断打乱的,二叉查找树。

$~\$


$\quad\quad$ $Splay$,也叫伸展树,本质上类似二叉查找树,是一种平衡树…

$\quad\quad$ 什么叫平衡树?我们上面其实已经提到了,平衡树就是一类用各种方法使出题人没办法把我们卡成 $O(n)$ 的 BST。

$\quad\quad$ 我们上面还提到了一种 “平衡” 的方式:在每次操作时进行打乱。这是一个朴素但有效的想法(其实还有更朴素的,那就是替罪羊树的直接重构)。

$\quad\quad$ 这所谓的 打乱 操作,正对应着 $Splay$ 的伸展($Splay$)。(严格来讲,这不能叫打乱,要叫平衡)

$\quad\quad$ $Splay$ 主要分为两种,一种是维护权值的 $Splay$,一种是直接维护序列的 $Splay$,后者与一般 BST 有一定差异。

$\quad\quad$ 先介绍前者,维护权值的 $Splay$ 。它其实就是一棵可以自我平衡的 BST,BST 能处理的它能处理,BST 不能处理的它有可能也能处理,下面简单介绍它都能处理什么问题。

$~\$


$\quad\quad$ 先给出变量列表,从这里面就可以看出很多东西了:

  const int N=100010;

  int num[N];//编号为i的点,代表的数值是多少...
  int cnt[N];//编号为i的点,代表的数值出现了多少次...
  int fa[N],son[N][2];//编号为i的点,父亲与左右儿子编号各是多少...
  int size[N];//以编号为i的点为根的子树的节点的cnt的和是多少...

  int tot;//计数工具:最后一个新建的点的编号是多少
  int root;//Splay的根的编号是多少 

$\quad\quad$ 我们一个一个看:

$\quad\quad$ $num$ 和 $cnt$ 好理解,我们一般的 BST 相同的元素是分成不同的点的,这里只不过把它们压缩成了一个点而已。

$\quad\quad$ $fa,son$ 也好理解,二叉树嘛,总要构建出树的结构的。

$\quad\quad$ $size$ 上面讲过了,用来处理操作的,也不难理解。

$\quad\quad$ 是不是突然发现 $Splay$ 的变量都挺好理解的?

$\quad\quad$ 下面看看 $Splay$ 的几大核心操作。

$~\$


$rotate$(旋转):

$\quad\quad$ 旋转,是我们的打乱操作的基础,也就是我们 $Splay$ 的核心: $Splay$ 操作的基础。

$\quad\quad$ 它的作用是:在不改变树的本质的前提下,调整几个节点之间的位置关系。

$\quad\quad$ 就像我们玩俄罗斯方块一样,先把方块转几圈,再放下去才能得高分。

$\quad\quad$ 上图:(以下所有点上的数字,仅代表该节点的编号,不代表该节点的数值)

$\quad\quad$ 这是一棵很 长 的树。看起来不是很平衡的样子......

$\quad\quad$ 我们让 $4$ 号节点上旋…得到:

$\quad\quad$ 是不是平衡多了?嗯?你说啥?你问这是咋操作的?

$\quad\quad$ 让我们来给这些节点染点颜色。

$\quad\quad$ 旋转前:

$\quad\quad$ 旋转后:

$\quad\quad$ 是不是稍微有点明白 “旋转” 啥意思了?

$\quad\quad$ 下面是详细的旋转步骤:

1:设旋转的节点为x点,其父节点为y点,祖父节点为z点...
2:设x是y的m儿子(m为0/1,代表左/右儿子,下同),y是z的n儿子...
3:把x的m^1儿子变为y的m儿子
4:把y变为x的m^1儿子
5:把x变为z的n儿子
6:更新操作后x,y的size值(为什么其他点不用更新?因为它们的儿子都没变的来着)

$\quad\quad$ 上面的 ^ 代表的是 $\oplus$,即异或。

$\quad\quad$ 虽然过程看起来很复杂,但其实只有 $3,4,5$ 三步比较关键,需要记忆。

$\quad\quad$ 下面是代码描述,从上到下分别于上面的步骤相对应:

  void rotate(int x)
  {
      int y = fa[x], z = fa[y];

      int m = find(x) , n = find(f);

      connect(son[x][m ^ 1], y, m);

      connect(y, x, m ^ 1);

      connect(x, z, n);

      push_up(y), push_up(x);
  }

$\quad\quad$ 注意了:三个 $connect$ 和两个 $push_up$ 的顺序一定不能反。

$\quad\quad$ 对了,$find(),connect(),push_up()$是三个辅助函数,作用分别为:得到某个节点是它父亲的什么儿子;连接某两个点;更新某个点的$size$值…其代码如下:

  int find(int x)
  {
      return son[fa[x]][1] == x ? 1 : 0;
  }

  void connect(int x, int y, int w_son)
  {
      if(y) son[y][w_son] = x;
      if(x) fa[x] = y;
  }

  void push_up(int x)
  {
      size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
  }

$\quad\quad$ 注意了:$connect$函数一定不能把0点与其他点连起来,要么你在 $connect$ 里面判一下,要么你在以后调用 $connect$ 之前判一下。(这都是血的教训啊)


$~\$

$Splay$(伸展):

$\quad\quad$ 理解了 $rotate$ 之后, $Splay$ 就好理解了…如果说 $rotate$ 是旋转俄罗斯方块,那么 $Splay$ 就要通过一次次的旋转把俄罗斯方块消掉了。

$\quad\quad$ $Splay$ 本质是:把一个节点不断网上旋,直到到根(或者某指定节点)。

$\quad\quad$ 你可能很疑惑,为什么这样就可以把整棵树给平衡了…关于 $Splay$ 的均摊时间复杂度分析有很多论文,感兴趣可以搜一搜,这里就不详细讲了。

$\quad\quad$ $Splay$ 操作起来就很简单了,一直旋到根而已,代码如下。(下面代码压了行,所以可能有些难以理解,展开之后就好理解多了)

  void Splay(int x)
  {
      for(int f; (f = fa[x]) != 0; rotate(x))
          if(fa[f]) rotate(find(f) == find(x) ? f : x);

      root = x;
  }

$\quad\quad$ 不过,可以看出,旋转过程中有一个特殊情况:当旋转节点,旋转节点父节点,旋转节点祖父节点“三点一线”(旋转节点是父节点的m儿子,父节点也是祖父节点的m儿子)时,要先转一下父节点,再转一下当前节点…为什么?移步 $Splay$ 复杂度分析论文,请。

$\quad\quad$ 注意了:最后不要忘了把根赋给旋上来的节点(如果它是一直旋到根的话)。

$\quad\quad$ $Splay$ 这个平衡操作咋用呢?很简单,每次操作后给被操作节点一个 $Splay$ 就好。


$~\$

$\quad\quad$ 接下来就直接上代码了…都是些常用的函数…


$~\$

$Find$(得到某个点的排名):

  int Find(int x)
  {
      int now = root, ans = 0;

      while(true)
      {
          if(x < num[now])
          {
              now = son[now][0];
              continue;
          }

          ans += size[son[now][0]];

          if(num[now] == x)
          {
              Splay(now);
              return ans + 1;
          }

          ans += cnt[now];

          now = son[now][1];
      }
  }

$~\$

$Kth$(得到排行为x的节点的值):

  int Kth(int rank)
  {
      int now = root;

      while(1)
      {
          if(rank <= size[son[now][0]])
          {
              now = son[now][0];
              continue;
          }
          rank -= size[son[now][0]];

          if(rank <= cnt[now])
          {
              Splay(now);
              return num[now];
          }
          rank -= cnt[now];

          now = son[now][1];
      }
  }

$~\$

$Insert$(插入):

$\quad\quad$ 这个函数要注意一下,好理解但操作比较多,不要掉了哪一个。

  void Insert(int x)
  {
      if(root == 0)
          root = ++tot, size[tot] = cnt[tot] = 1, num[tot] = x;
      else
      {
          int now = root, f = 0;

          while(true)
          {
              if(num[now] == x)
              {
                  cnt[now]++;
                  push_up(now), push_up(f);
                  Splay(now);

                  return ;
              }

              f = now, now = son[now][x > num[now]];

              if(!now)
              {
                  num[++tot] = x, size[tot] = cnt[tot] = 1;
                  fa[tot] = f, son[f][x > num[f]] = tot;
                  push_up(f), Splay(tot);

                  return ;
              }
          }
      }
  }

$~\$

$Delete$(删除):

$\quad\quad$ 与一般 BST 的删除不同,因为我们有 $Splay$ 操作,所以我们可以通过 $Find$ 操作把要删的点直接转到根上来,然后分情况讨论处理就好,注意:要在操作前把原本的根记录下来,后面的 $Splay$ 操作会改变根(记录用的变量名不要和 $root$ 太像…我用 $rt$ 时弄混好多次了)。

$\quad\quad$ 这里的 $clear$ 操作就是一个简单的把某个点的各个数据全部清零的操作。

  void Delete(int x)
  {
      Find(x);

      int now = root;

      if(cnt[now] > 1) cnt[now]--, size[now]--;
      else if(!son[now][0] && !son[now][1])
          root = 0, clear(now);
      else if(!son[now][0] && son[now][1])
          fa[root = son[now][1]] = 0, clear(now);
      else if(son[now][0] && !son[now][1])
          fa[root = son[now][0]] = 0, clear(now);
      else
      {
          int pre = Pre(), rt = root, rson = son[root][1];

          Splay(pre), connect(rson, pre, 1);
          clear(rt), push_up(root);
      }
  }

$~\$

$Pre$(得到根的前驱的编号):

  int Pre()
  {
      int now = son[root][0];
      while(son[now][1])
          now = son[now][1];
      return now;
  }

$~\$

$Suc$(得到根的后继的编号):

  int Suc()
  {
      int now = son[root][1];
      while(son[now][0])
          now = son[now][0];
      return now;
  }

$\quad\quad$ 以上是$Splay$的基本操作。

  • 代码:
  #include <bits/stdc++.h>

  using namespace std;

  const int N = 100010;

  int fa[N], son[N][2], cnt[N], num[N] , size[N];

  int n, tot, root;

  void clear(int x)
  {
      fa[x] = son[x][0] = son[x][1] = cnt[x] = num[x] = size[x] = 0;
  }

  int find(int x)
  {
      return son[fa[x]][1] == x ? 1 : 0;
  }

  void connect(int x, int y, int w_son)
  {
      if(y) son[y][w_son] = x;
      if(x) fa[x] = y;
  }

  void push_up(int x)
  {
      size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
  }

  void rotate(int x)
  {
      int f = fa[x], ff = fa[f] , k = find(x) , i = find(f);

      connect(son[x][k ^ 1], f, k);
      connect(f, x, k ^ 1);
      connect(x, ff, i);
      push_up(f), push_up(x);
  }

  void Splay(int x)
  {
      for(int f; (f = fa[x]) != 0; rotate(x))
          if(fa[f]) rotate(find(f) == find(x) ? f : x);

      root = x;
  }

  void Insert(int x)
  {
      if(root == 0)
          root = ++tot, size[tot] = cnt[tot] = 1, num[tot] = x;
      else
      {
          int now = root, f = 0;

          while(true)
          {
              if(num[now] == x)
              {
                  cnt[now]++;
                  push_up(now), push_up(f);
                  Splay(now);

                  return ;
              }

              f = now, now = son[now][x > num[now]];

              if(!now)
              {
                  num[++tot] = x, size[tot] = cnt[tot] = 1;
                  fa[tot] = f, son[f][x > num[f]] = tot;
                  push_up(f), Splay(tot);

                  return ;
              }
          }
      }
  }

  int Find(int x)
  {
      int now = root, ans = 0;

      while(true)
      {
          if(x < num[now])
          {
              now = son[now][0];
              continue;
          }

          ans += size[son[now][0]];

          if(num[now] == x)
          {
              Splay(now);
              return ans + 1;
          }

          ans += cnt[now];

          now = son[now][1];
      }
  }

  int Kth(int rank)
  {
      int now = root;

      while(1)
      {
          if(rank <= size[son[now][0]])
          {
              now = son[now][0];
              continue;
          }
          rank -= size[son[now][0]];

          if(rank <= cnt[now])
          {
              Splay(now);
              return num[now];
          }
          rank -= cnt[now];

          now = son[now][1];
      }
  }

  int Pre()
  {
      int now = son[root][0];
      while(son[now][1])
          now = son[now][1];
      return now;
  }

  int Suc()
  {
      int now = son[root][1];
      while(son[now][0])
          now = son[now][0];
      return now;
  }

  void Delete(int x)
  {
      Find(x);

      int now = root;

      if(cnt[now] > 1) cnt[now]--, size[now]--;
      else if(!son[now][0] && !son[now][1])
          root = 0, clear(now);
      else if(!son[now][0] && son[now][1])
          fa[root = son[now][1]] = 0, clear(now);
      else if(son[now][0] && !son[now][1])
          fa[root = son[now][0]] = 0, clear(now);
      else
      {
          int pre = Pre(), rt = root, rson = son[root][1];

          Splay(pre), connect(rson, pre, 1);
          clear(rt), push_up(root);
      }
  }

  int main()
  {
      scanf("%d", &n);
      for(int k = 1; k <= n; k++)
      {
          int opt, x;
          scanf("%d %d", &opt, &x);

          if(opt == 1)
              Insert(x);
          else if(opt == 2)
              Delete(x);
          else if(opt == 3)
              printf("%d\n", Find(x));
          else if(opt == 4)
              printf("%d\n", Kth(x));
          else if(opt == 5)
              Insert(x), printf("%d\n", num[Pre()]), Delete(x);
          else
              Insert(x), printf("%d\n", num[Suc()]), Delete(x);
      }

      return 0;
  }

$~\$


$~\$


$\quad\quad$ $Splay$ 不仅可以完成上面的 BST 共有操作,还可以维护序列,这也是它能成为 LCT 辅助树的原因之一。

$\quad\quad$ 首先,$Splay$ 有一个显然的性质:在不增加/删除节点的前提下,无论怎么旋转,$Splay$ 的本质都不会改变,其中序遍历也不会改变

$\quad\quad$ 中序遍历的不变性是 $Splay$ 维护序列的基础,我们把原序列中各个数的位置和其在 $Splay$ 中的中序遍历序号依次对应,就可以完成由序列到 $Splay$ 的转换。

$\quad\quad$ 简单的说,就是:我们依次把序列中的数往 $Splay$ 最右侧的位置插(对应最大的中序遍历值),最后插出来的 $Splay$ 的中序遍历就是我们要的序列,且这个序列在进行 $Splay$ 操作后不会改变。

$\quad\quad$ (维护序列的 $Splay$ 实质其实是一棵以元素在序列中的位置为关键字的 BST)

$\quad\quad$ 下面,我们借助例题加以解释。

$\quad\quad$ 简单的说,本题要求维护一个支持区间翻转的序列。

$\quad\quad$ 为什么区间翻转可以用 $Splay$ 维护?

$\quad\quad$ 首先,我们可以简单的在 $Splay$ 中提取一个区间:把序列中第 $r+1$ 个点 $A$ 转到根,把序列中第 $l-1$ 个点 $B$ 转成根的左儿子,那么 $B$ 的右儿子对应的子树包含 $l-r$ 区间内的所有值。

$\quad\quad$ 为什么?我们前面提到了,这里的 $Splay$ 本质上是一棵以元素在序列中的位置为关键字的 BST,那么 $B$ 右子树中的所有节点在序列中的位置就应该大于 $l-1$,小于 $r+1$。

$\quad\quad$ 还有一个问题:我们怎么得到序列中第 $x$ 个点在 $Splay$ 中的编号?根据数组下标与中序遍历的对应原则,我们找 $Splay$ 中中序遍历为 $x$ 的点即可。(不知道怎么找?给个提示吧:我们之前找第 $K$ 小的数,本质上也是找中序遍历为 $x$ 的点)

$\quad\quad$ 好,我们把区间提取出来了,但怎么翻转呢?

$\quad\quad$ 很简单,交换子树中所有节点的左右儿子即可。

$\quad\quad$ 放图(在原序列中翻转区间$[2,4]$,点上的数值代表该项的权值):

$\quad\quad$ 开始时:(中序遍历为1 2 3 4 5)

$\quad\quad$ 旋转节点1(B点),节点5(A点)。(不要忘了三点一线是特殊处理的)

$\quad\quad$ 我们发现,所有要翻转的点都在1点的右子树上,如下图…

$\quad\quad$ 交换左右儿子…(中序遍历为 1 4 3 2 5)

$~\$


$\quad\quad$ 好了,翻完了…显然这个过程中可以打个懒惰标记…标记的打法类似线段树,记得每次向下前把标记打下来就行了。

$\quad\quad$ 至于最后输出时,中序遍历整个$Splay$即可。

$\quad\quad$ 另外,有一个小技巧:为了防止翻转时调用$l-1,r+1$越界,我们可以在开始时在左右两侧分别加入两个值。

$~\$


  • 代码:
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

inline int read();

//rev 为懒惰标记,没有比较记录点的权值
int son[N][2], fa[N], siz[N], rev[N];
int n, m, rt, tot;

//-----辅助函数-----//
//因为不删节点,就没必要有 clear 了

void connect(int x, int y, int z)
{
    if(x) fa[x] = y;
    if(y) son[y][z] = x;
}
void push_up(int x)
{
    siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
}
//下放懒惰标记
void push_down(int x)
{
    if(rev[x])
    {
        swap(son[x][0], son[x][1]);
        rev[x] ^= 1, rev[son[x][0]] ^= 1, rev[son[x][1]] ^= 1;
    }
}
int find(int x)
{
    return x == son[fa[x]][1];
}

void rotate(int x)
{
    int y = fa[x], z = fa[y], k = find(x), i = find(y);

    connect(son[x][k ^ 1], y, k);
    connect(y, x, k ^ 1);
    connect(x, z, i);

    push_up(y), push_up(x);
}

void Splay(int x, int to)
{
    //一定是先从根节点,向下找到某个节点,再进行的 Splay
    //所以 Splay 所在的点及其路径上的点一定是没有标记的
    for(int f; (f = fa[x]) != to; rotate(x))
        if(fa[f] != to) rotate(find(x) == find(f) ? f : x);
    if(!to) rt = x;
}

//-----主要函数-----//

//插入建树,直接像线段树那样creat也可以
void Insert()
{
    if(!rt)
    {
        siz[rt = ++tot] = 1;
        return ;
    }

    //一路向右插就可以了
    int now = rt, f = 0;
    while(now)
        f = now, now = son[now][1];
    siz[now = ++tot] = 1, connect(now, f, 1);
    Splay(now, 0);
}

//查询下标为 x 的数的编号
int Kth(int x)
{
    int now = rt;
    while(1)
    {
        //不要忘了下放标记
        push_down(now);

        if(x <= siz[son[now][0]])
        {
            now = son[now][0];
            continue;
        }
        x -= siz[son[now][0]];

        if(x == 1) return now;
        x--, now = son[now][1];
    }
}

//翻转某棵子树
void Reverse(int x)
{
    rev[x] ^= 1;
}

//操作处理有点麻烦,单独拿出来处理
void work(int l, int r)
{
    //找到需要翻的两个点
    int L = Kth(l - 1), R = Kth(r + 1);
    //把两个点翻到对应的位置上
    Splay(R, 0), Splay(L, R);
    //翻转已经提取出的整棵树
    Reverse(son[L][1]);
}

//中序遍历输出
void Dfs(int x)
{
    if(!x) return ;
    //不要忘了下放标记
    push_down(x);
    Dfs(son[x][0]);

    //别输出左右两个加进去的点了
    if(x >= 2 && x <= n + 1)
        printf("%d ", x - 1);
    Dfs(son[x][1]);
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n + 2; k++)
        Insert();

    for(register int k = 1; k <= m; k++)
    {
        int l = read(), r = read();
        //前面加了一个点,对应操作下标要加一
        work(l + 1, r + 1);
    }

    Dfs(rt);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\$


结语:

$\quad\quad$ 最后是刷题表:

$\quad\quad$ 洛谷 P3165 [CQOI2014]排序机械臂(段维护板子)

$\quad\quad$ 洛谷 P2073 送花(极水的板子)

$\quad\quad$ 洛谷 P2343 宝石管理系统(更水的板子)

$\quad\quad$ 洛谷 P2286 [HNOI2004]宠物收养场 (有点麻烦…)

$\quad\quad$ 洛谷 P4146 序列终结者 (段维护板子$PLUS$)

$\quad\quad$ 洛谷 P2042 [NOI2005]维护数列 (超级码力)

$
$

$$\huge\color {#123456} \mathcal {E \ N \ D}$$




应该不会有人跑去写斐波那契堆的吧?

Latex 已炸,建议 Goto 原网址: https://xjx885.coding-pages.com/post/u3KjOvd_5/

[HTML_REMOVED]

前言:

$~\$

$\quad\quad$ 日常做笔记。


$~\$

正文:

$\quad\quad$ 配对堆是可并堆的一种,支持快速插入元素,合并两个堆,删除堆顶元素,更改堆顶元素的值,但在 OI 界较为冷门。

$\quad\quad$ 存储:其本质上是一颗树的结构,但存储时只存储某个节点的左儿子与右兄弟。

$\quad\quad$ 就像下面这两幅图:前者是一棵树,后者是配对堆,后者本质上就是前者,但二者存储方式不同。

$~\$

$~\$

$\quad\quad$ 合并:其合并操作非常简单,如果是小根堆,就把根大的堆往根小的堆上面贴就好了,反之亦然。

$\quad\quad$ 代码($a,b$ 是待合并的两个堆的根节点,返回值为合并后的根):


int merge(int a, int b)
{
    if(!a || !b || a == b) return a ? a : b;
    //如果该操作有意义
    if(d[a] < d[b]) swap(a, b);
    //强制让a往b上贴

    point[a].xd = point[b].son , point[b].son = a;
    return b;
}

$\quad\quad$ 插入:插入节点的话,把新节点作为一个单独的堆 $\operatorname{merge}$ 进来就好了,合并和插入的复杂度显然是 $O(1)$。

$~\$

$~\$

$\quad\quad$ 修改:配对堆的修改分两种情况(以小根堆为例),第一种是把某一个值改大(一般不用),第二种是把某一个值改小。

$\quad\quad$ 第一种操作会破坏该节点的子树结构,所以没办法高效的完成,只能把以该节点为根的子树剖出来,然后删去它的最小值(该节点),插入该节点修改后的值,最后与原堆合并。复杂度与删去节点(该操作在下面)的复杂度相同($O(logn)$)。

$\quad\quad$ 第二种操作不会破坏该节点的子树结构,可以直接剖出以该节点为根的子树,修改该节点的值,然后与原堆合并即可,复杂度显然是 $O(1)$,但因为会破坏原有势能分析过程,导致其均摊复杂度不好计算。

$\quad\quad$ 这里就不放代码了,这操作不咋常用。

$~\$

$~\$

$\quad\quad$ 删除:删除是配对堆最麻烦的操作,一个朴素的想法是:删除堆顶节点时,把堆顶节点的儿子从左往右一个个 $\operatorname {merge}$ 到一起,形成一个新的堆,然后把原来的堆顶节点丢掉就好。如果删除的不是堆顶节点,把它剖出来再操作即可。

$\quad\quad$ 这样做复杂度显然是 $O(n)$ 的,承受不起。

$\quad\quad$ 降低复杂度的一个很好方法是 “配对”,即从左往右把根的儿子两两合并成二元组,然后从右往左把这些二元组依次合并。

$\quad\quad$ 如下图,删除之前用树形结构表示,删除过程(P2~P4)用存储结构(左儿子右兄弟)表示:

$\quad\quad$ 显然,这里任然 $\operatorname{merge}$ 了 $n-1$ 次,但是其均摊复杂度是 $O(logn)$ 的,具体证明可以去翻配对堆论文。

$\quad\quad$ 代码:

$\quad\quad$ 递归合并部分:

int merges(int x)
{
    if(!x) return 0;
    if(!xd[x]) return x;

    int a = xd[x], b = xd[a];
    return merge(merge(x, a), merges(b));
}

$\quad\quad$ 调用删除节点 $a$ 时直接 merge(son[a]) 就行了。

$~\$

$~\$

$\quad\quad$ 例题:P3377 【模板】左偏树(可并堆)

$\quad\quad$ 本题中,给出要求合并的点并不一定是根节点,所以要用并查集维护每个点所在堆的根节点。

$\quad\quad$ 注意:配对堆用带路径压缩的并查集维护根节点是谁时,在删去某个节点后,需要把该节点的 $fa$ 指向新建出的堆的根节点,否则并查集的查询链会断掉。

$\quad\quad$ 代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

inline int read()
{
    int x = 0, ch = '~', fh = 1;

    while(!isdigit(ch)) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

int n, m, d[N], fa[N], del[N];

struct node
{
    int son, xd;
} point[N];

int merge(int a, int b)
{
    if(!a || !b || a == b) return (!a) ? b : a;
    if(d[a] < d[b] || d[a] == d[b] && a < b) swap(a, b);

    point[a].xd = point[b].son , point[b].son = a;
    return fa[a] = b;
}

int merges(int x)
{
    if(!x ) return 0;
    fa[x] = x;
    if(!point[x].xd) return x;

    int a = point[x].xd, b = point[a].xd;
    fa[a] = a, point[x].xd = point[a].xd = 0;
    return merge(merge(x, a), merges(b));
}

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        d[k] = read(), fa[k] = k;

    for(register int k = 1; k <= m; k++)
    {
        int opt = read(), x = read(), y;
        if(opt == 1) y = read();

        if(opt == 1)
        {
            if(!del[x] && !del[y])
                merge(find(x), find(y));
        }

        else if(!del[x])
        {
            int top = find(x);

            printf("%d\n", d[top]), del[top] = 1;
            fa[top] = merges(point[top].son);
        }
        else
            printf("-1\n");
    }

    return 0;
}

$~\$

$~\$

$\quad\quad$ 树上操作例题:P1552 [APIO2012]派遣

$\quad\quad$ 其实是差不多的,把序列上的操作放在树上, $dfs$ 分别处理就好。

$\quad\quad$ 代码:

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1000010;

inline int read()
{
    int x = 0, ch = '~';

    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x;
}

int n, m, C[N], add[N], size[N], L[N], fa[N], lson[N], rxd[N];
vector <int > son[N];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int merge(int u, int v)
{
    if(!u || !v || u == v) return u ? u : v;
    if(C[u] > C[v]) swap(u, v);

    rxd[u] = lson[v], lson[v] = u, add[v] += add[u], size[v] += size[u];
    return fa[u] = v;
}

int merges(int x)
{
    if(!x) return 0;
    if(!rxd[x]) return x;

    int a = rxd[x], b = rxd[a];
    return merge(merge(x, a), merges(b));
}

int pop(int x)
{
    fa[x] = merges(lson[x]);
    return fa[x];
}

int answ;

void dfs(int root)
{
    int now = find(root);
    answ = max(answ, size[now] * L[root]);
    for(register int k = 0; k < (int )son[root].size(); k++)
    {
        int to = son[root][k];
        dfs(to), now = merge(find(now), find(to));
        while(add[now] > m) now = pop(now);
        answ = max(answ, size[now] * L[root]);
    }
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
    {
        int v = read();
        if(v) son[v].push_back(k);
        add[k] = C[k] = read(), L[k] = read(), fa[k] = k, size[k] = 1;
    }

    dfs(1);

    printf("%lld",answ);

    return 0;
}

结语:

$\quad\quad$ 话说会有人闲的没事干在比赛中写斐波那契堆的吗?

$$\large\color {#123456} {E \ N \ D}$$




嘛…稍微复习一下线段树好了…

因为是复习笔记,所以讲的很简略,也只讲了基础的东西,还留了很多坑…

填坑的话…省选后要是没 AFO 再说吧…Latex 炸的有点厉害,去我 Blog 看会好很多:https://xjx885.coding-pages.com/post/pyrz7nPvO/

[HTML_REMOVED]

前言:

$\qquad$ 线段树大概是用的最多的树形数据结构了吧?

$\qquad$ 比起其他数据结构,线段树板子没啥难度,难度下界很低。

$\qquad$ 但因为它可以添加很多区间标记,它的难度上界却又相当高…

$\qquad$ 啧啧......


$~\$

正文:

$\qquad$ 线段树基础操作(区间加减乘赋值极值和)就不讲了,直接上三道模板题:

$~\$

  • 解析:区间加,区间求和都是基操…

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define int long long

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay, sum, siz;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = tree[lc].sum + tree[rc].sum;
  }

  void push_down(int root)
  {
      if(tree[root].delay)
      {
          int D = tree[root].delay;
          tree[lc].delay += D, tree[rc].delay += D;
          tree[lc].sum += tree[lc].siz * D;
          tree[rc].sum += tree[rc].siz * D;
          tree[root].delay = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, int key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay += key;
          tree[root].sum += key * tree[root].siz;
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return Sum(lc, l, mid) + Sum(rc, mid + 1, r);
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read(), y = read();
          if(opt - 1)
              printf("%lld\n", Sum(rt, x, y));
          else
              Add(rt, x, y, read());
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$~\$

$~\$

  • 解析:上一题的升级版,板子升级后还是板子…

  • 代码:

  //调了一个小时...
  //我神仙地敲了个 M(x,y*1ll)
  //展开后就是 x=x*y*1ll%p,直接爆 int Orz...

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)
  #define M(a,b) (a = a * b % p)
  #define MOD(x) (x = x % p)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay1, delay2, sum, siz;
  } tree[N * 2];

  int n, m, p, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = (tree[lc].sum + tree[rc].sum) % p;
  }

  void push_down(int root)
  {
      if(tree[root].delay2 != 1)
      {
          long long D = tree[root].delay2;
          M(tree[lc].delay2, D), M(tree[rc].delay2, D);
          M(tree[lc].delay1, D), M(tree[rc].delay1, D);
          M(tree[lc].sum, D), M(tree[rc].sum, D);
          tree[root].delay2 = 1;
      }
      if(tree[root].delay1)
      {
          long long D = tree[root].delay1;
          tree[lc].delay1 += D, tree[rc].delay1 += D;
          MOD(tree[lc].delay1), MOD(tree[rc].delay1);
          tree[lc].sum += tree[lc].siz * D % p, MOD(tree[lc].sum);
          tree[rc].sum += tree[rc].siz * D % p, MOD(tree[rc].sum);
          tree[root].delay1 = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r, tree[root].delay2 = 1;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, long long key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay1 += key, MOD(tree[root].delay1);
          tree[root].sum += key * tree[root].siz % p, MOD(tree[root].sum);
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  void Mul(int root, int l, int r, long long key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          M(tree[root].delay2, key);
          M(tree[root].delay1, key);
          M(tree[root].sum, key);
          return ;
      }

      push_down(root);
      if(r <= mid) Mul(lc, l, r, key);
      else if(l > mid) Mul(rc, l, r, key);
      else Mul(lc, l, mid, key), Mul(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return (Sum(lc, l, mid) + Sum(rc, mid + 1, r)) % p;
  }

  signed main()
  {
      n = read(), m = read(), p = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read() % p;
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read(), y = read();
          if(opt == 1)
              Mul(rt, x, y, read() % p);
          else if(opt == 2)
              Add(rt, x, y, read() % p);
          else
              printf("%d\n", Sum(rt, x, y));
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$~\$

$~\$

  • 解析:不知道为啥这题算线段树模板3......这玩意是吉司机线段树…不咋考的知识点…用来完成区间最值操作和区间历史最值操作…有兴趣的可以看洛谷日报,这里不详细讲了。

  • 代码:忘了,懒得敲了…

$~\$

$~\$

$\qquad$ 模板放完了,下面再放点拓展题。

$~\$

  • 解析:第一眼我看成了李超树…敲到一半才发现是加法…题目不难,抓住等差数列的性质:$a_{i+1}-a_{i}=d$,我们不妨丢弃原始序列,用线段树/树状数组维护其差分序列,这样,加等差数列可以看做区间加,求某个点的值可以看做区间和,裸上线段树就完事了。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay, sum, siz;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = tree[lc].sum + tree[rc].sum;
  }

  void push_down(int root)
  {
      if(tree[root].delay)
      {
          int D = tree[root].delay;
          tree[lc].delay += D, tree[rc].delay += D;
          tree[lc].sum += tree[lc].siz * D;
          tree[rc].sum += tree[rc].siz * D;
          tree[root].delay = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, int key)
  {
      if(r < l) return ;

      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay += key;
          tree[root].sum += key * tree[root].siz;
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return Sum(lc, l, mid) + Sum(rc, mid + 1, r);
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      for(register int k = n; k >= 1; k--)
          d[k] = d[k] - d[k - 1];
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read();
          if(opt - 1)
              printf("%d\n", Sum(rt, 1, x));
          else
          {
              int y = read(), z = read(), c = read();
              Add(rt, x + 1, y, c), Add(rt, x, x, z);
              if(y + 1 <= n)Add(rt, y + 1, y + 1, c * (x - y) - z);
          }
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\$

$~\$

$\qquad$ 上面那题对线段树维护的序列进行了处理,使得原本不好维护的序列变得可维护,在解决复杂线段树问题时,这是一种很重要的思路。

$\qquad$ 下面这道例题则着重于对线段树本身进行扩展,即各种标记的设计,上传,下放,冲突。

$~\$

  • 解析:操作有点多,我们先从询问看起($3,4$操作), $3$ 操作比较好说,我们只要维护区间中 $0/1$ 任意一个的数量就好,$0,1$ 操作可以直接打 $Lazy$ 标记,$2$ 操作可以额外维护一个 $reverse$ 标记。$4$ 操作时线段树中常见的最长连续段问题,我们可以维护区间内最长连续段长度,包含区间左端点的最长连续段长度,包含区间右端点的最长连续段长度,然后合并即可,但麻烦的地方在于 $2$ 操作会直接影响到 $4$ 操作的维护过程…所以我们不仅得维护 $1$ 的最长连续段长度,还要维护 $0$ 的最长连续段长度......也是相当复杂了。

  • 总结:我们得维护区间 $0$(或者 $1$) 数目(与 $0,1,3$操作有关),$Lazy$ 标记(与 $0,1,3$ 操作有关),$reverse$ 标记(与 $2,3,4$ 操作有关),区间 $0$ 和 $1$ 的最长连续段与左右最长连续段的长度(与 $0,1,2,4$ 操作有关)。

  • 代码:我调了两个小时来着…

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs, siz;
      int d, num_1, rev;
      int l1, r1, max1;
      int l0, r0, max0;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].num_1 = tree[lc].num_1 + tree[rc].num_1;
      tree[root].l0 = (tree[lc].l0 == tree[lc].siz ? tree[lc].siz + tree[rc].l0 : tree[lc].l0);
      tree[root].l1 = (tree[lc].l1 == tree[lc].siz ? tree[lc].siz + tree[rc].l1 : tree[lc].l1);
      tree[root].r0 = (tree[rc].r0 == tree[rc].siz ? tree[rc].siz + tree[lc].r0 : tree[rc].r0);
      tree[root].r1 = (tree[rc].r1 == tree[rc].siz ? tree[rc].siz + tree[lc].r1 : tree[rc].r1);
      tree[root].max0 = max(max(tree[lc].max0, tree[rc].max0), tree[lc].r0 + tree[rc].l0);
      tree[root].max1 = max(max(tree[lc].max1, tree[rc].max1), tree[lc].r1 + tree[rc].l1);
  }

  void push_down(int root)
  {
      if(tree[root].rev)
      {
          if(tree[lc].d != -1) tree[lc].d ^= 1;
          if(tree[rc].d != -1) tree[rc].d ^= 1;
          swap(tree[lc].l0, tree[lc].l1), swap(tree[rc].l0, tree[rc].l1);
          swap(tree[lc].r0, tree[lc].r1), swap(tree[rc].r0, tree[rc].r1);
          swap(tree[lc].max0, tree[lc].max1), swap(tree[rc].max0, tree[rc].max1);
          tree[lc].num_1 = tree[lc].siz - tree[lc].num_1;
          tree[rc].num_1 = tree[rc].siz - tree[rc].num_1;

          tree[root].rev = 0;
          tree[lc].rev ^= 1, tree[rc].rev ^= 1;
      }
      if(tree[root].d != -1)
      {
          if(tree[root].d == 1)
          {
              tree[lc].l0 = tree[lc].r0 = tree[lc].max0 = 0;
              tree[lc].l1 = tree[lc].r1 = tree[lc].max1 = tree[lc].siz;
              tree[rc].l0 = tree[rc].r0 = tree[rc].max0 = 0;
              tree[rc].l1 = tree[rc].r1 = tree[rc].max1 = tree[rc].siz;
              tree[lc].num_1 = tree[lc].siz, tree[rc].num_1 = tree[rc].siz;
          }
          else
          {
              tree[lc].l0 = tree[lc].r0 = tree[lc].max0 = tree[lc].siz;
              tree[lc].l1 = tree[lc].r1 = tree[lc].max1 = 0;
              tree[rc].l0 = tree[rc].r0 = tree[rc].max0 = tree[rc].siz;
              tree[rc].l1 = tree[rc].r1 = tree[rc].max1 = 0;
              tree[lc].num_1 = tree[rc].num_1 = 0;
          }

          tree[lc].d = tree[rc].d = tree[root].d;
          tree[root].d = -1;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r, tree[root].d = -1;

      if(l == r)
          if(d[l])
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = 1;
          else
              tree[root].l0 = tree[root].r0 = tree[root].max0 = 1;
      else
          Creat(lc, l, mid), Creat(rc, mid + 1, r), push_up(root);
  }

  void Change(int root , int l, int r, int key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].d = key;
          if(key)
          {
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = tree[root].siz;
              tree[root].l0 = tree[root].r0 = tree[root].max0 = 0;
          }
          else
          {
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = 0;
              tree[root].l0 = tree[root].r0 = tree[root].max0 = tree[root].siz;
          }
          return ;
      }

      push_down(root);
      if(r <= mid) Change(lc, l, r, key);
      else if(l > mid) Change(rc, l, r, key);
      else Change(lc, l, mid, key), Change(rc, mid + 1, r, key);
      push_up(root);
  }

  void Reverse(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].rev ^= 1;
          if(tree[root].d != -1) tree[root].d ^= 1;
          swap(tree[root].l0, tree[root].l1);
          swap(tree[root].r0, tree[root].r1);
          swap(tree[root].max0, tree[root].max1);
          tree[root].num_1 = tree[root].siz - tree[root].num_1;

          return ;
      }

      push_down(root);
      if(r <= mid) Reverse(lc, l, r);
      else if(l > mid) Reverse(rc, l, r);
      else Reverse(lc, l, mid), Reverse(rc, mid + 1, r);
      push_up(root);
  }

  int Query1(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].num_1;

      push_down(root);
      if(r <= mid) return Query1(lc, l, r);
      else if(l > mid) return Query1(rc, l, r);
      else return Query1(lc, l, mid) + Query1(rc, mid + 1, r);
  }

  struct Node
  {
      int Max, lmax, rmax;

      Node(int a, int b, int c)
      {
          Max = a, lmax = b, rmax = c;
      }
      Node() { }
  };

  Node Query2(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return Node(tree[root].max1, tree[root].l1, tree[root].r1);

      push_down(root);
      if(r <= mid) return Query2(lc, l, r);
      else if(l > mid) return Query2(rc, l, r);
      else
      {
          Node A = Query2(lc, l, mid), B = Query2(rc, mid + 1, r);
          int MAX = max(A.Max, max(B.Max, A.rmax + B.lmax));
          int LMAX = (A.lmax == mid - l + 1 ? A.lmax + B.lmax : A.lmax);
          int RMAX = (B.rmax == r - mid ? B.rmax + A.rmax : B.rmax);
          return Node(MAX, LMAX, RMAX);
      }
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), l = read() + 1, r = read() + 1;
          if(opt == 0) Change(rt, l, r, 0);
          else if(opt == 1) Change(rt, l, r, 1);
          else if(opt == 2) Reverse(rt, l, r);
          else if(opt == 3) printf("%d\n", Query1(rt, l, r));
          else printf("%d\n", Query2(rt, l, r).Max);
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\$

$~\$

$\qquad$ 上面那题难吗?一点都不难(所有操作都是基操)......然而在比赛中能调出线段树解法的人,大概非神即欧了吧…

$\qquad$ 下面简单介绍几个线段树的拓展模型和应用。

$~\$

$\qquad$ 猫树:本来应该先讲 ZKW线段树 的,但我一般不用那玩意…

$\qquad$ 猫树是一种维护满足结合律且要求快速合并的信息的静态线段树。

$\qquad$ 一般线段树在建树时进行了 $O(n)$ 次合并操作,猫树则需进行 $O(nlogn)$ 次,一般线段树查询时要进行 $O(logn)$ 次合并操作,猫树只需要 $O(1)$ 次,也就是说,查询操作会快很多(其实也还好来着)。

$\qquad$ 猫树的核心思路是:对区间 $[L,R]$,预处理出 $Sum_l(i)=\sum\limits_{j=i}^{mid}d(j),i\in[L,mid]$($d(j)$ 表示序列中 $j$ 位置的元素的值),同理预处理出 $Sum_r(i)=\sum\limits_{j=mid+1}^{i}d(j),i\in[mid+1,R]$,这样,如果有询问 $[l,r] \subset [L,R]$,我们可以把它视为 $[l,mid] \cup (mid,r]$,如果我们可以高效率地合并 $[l,mid]$ 和 $(mid,r]$,就可以更快地解决问题。

$\qquad$ 这要求信息不能修改且满足结合律。比如说区间和,区间最值等等,它们均可以 $O(1)$ 合并完成。

$\qquad$ 现在还剩下两个问题:

$\qquad$ 第一,怎么预处理 $Sum_{i/j}$ 数组。很显然,我们直接在 $creat$ 操作的时候对每个节点算出来就好了,画个图,可以直观感受到,存储它的空间复杂度是 $O(nlogn)$ 的,时间复杂度也如此。

$\qquad$ 第二,怎么确定每个 $[l,r]$ 区间对应哪个 $[L,R]$ 区间,我们是要保证 $mid$ 在 $[l,r]$ 里面的。这里直接给一个结论:我们设 $[l,l]$ 对应的节点编号为 $x$, $[r,r]$ 对应节点为 $y$,则满足条件的一个 $[L,R]$ 对应节点层数为 $log_2x-log_2{(x \oplus y)}$,预处理出 $log_2i$ 即可 $O(1)$ 算出。

$~\$

$~\$

  • 解析:猫树模板题,$M$ 要是再大一点就可以卡死普通线段树了。求的是最大连续子段和,可以看成左右两边的最大和和过中点的最大和的并。

  • 代码:

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 4e5 + 10;

inline int read();

#define mid ((l+r)>>1)

int n, n0, m, tot;
int d[N], cs[N], num[N], lg[N];
int Max[22][N][2], Cmax[22][N][2];
//最大和,过中点的最大和

void creat(int root, int l, int r, int C)
{
    cs[root] = C;
    if(l == r)
    {
        num[l] = root;
        return ;
    }
    else creat(root << 1, l, mid, C + 1), creat(root << 1 | 1, mid + 1, r, C + 1);

    Cmax[C][mid][0] = d[mid], Cmax[C][mid + 1][1] = d[mid + 1];
    for(register int k = mid - 1; k >= l; k--) Cmax[C][k][0] = Cmax[C][k + 1][0] + d[k];
    for(register int k = mid - 1; k >= l; k--) Cmax[C][k][0] = max(Cmax[C][k + 1][0], Cmax[C][k][0]);
    for(register int k = mid + 2; k <= r; k++) Cmax[C][k][1] = Cmax[C][k - 1][1] + d[k];
    for(register int k = mid + 2; k <= r; k++) Cmax[C][k][1] = max(Cmax[C][k - 1][1], Cmax[C][k][1]);
    Max[C][mid][0] = Max[C][mid][1] = d[mid];
    for(register int k = mid - 1; k >= l; k--) Max[C][k][0] = Max[C][k + 1][0] > 0 ? Max[C][k + 1][0] + d[k] : d[k];
    for(register int k = mid - 1; k >= l; k--) Max[C][k][0] = max(Max[C][k][0], Max[C][k + 1][0]);
    for(register int k = mid + 1; k <= r; k++) Max[C][k][1] = Max[C][k - 1][1] > 0 ? Max[C][k - 1][1] + d[k] : d[k];
    for(register int k = mid + 1; k <= r; k++) Max[C][k][1] = max(Max[C][k][1], Max[C][k - 1][1]);
}

signed main()
{
    n0 = read();
    for(register int k = 1; k <= n0; k++)
        d[k] = read();

    //把元素个数化为 2 的整数次幂
    for(n = 1; n < n0; n <<= 1);
    for(register int k = 2; k <= n * 2; k++)
        lg[k] = lg[k >> 1] + 1;
    creat(1, 1, n, 1);

    m = read();
    for(register int k = 1; k <= m; k++)
    {
        int x = read(), y = read();
        if(x == y)
        {
            printf("%lld\n", d[x]);
            continue;
        }

        int P = lg[num[x]] - lg[num[x] ^ num[y]];
        printf("%lld\n", max(Cmax[P][x][0] + Cmax[P][y][1], max(Max[P][x][0] , Max[P][y][1])));
    }

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\$

$~\$

$\qquad$ 扫描线:虚拟一条坐标系上不存在的不断移动的线来求矩形周长面积并等数据的方法。

$~\$

  • 解析:对于扫描线问题,我们一般虚拟一条不存在的横向直线,并让它从最低处向上一格一格地移动,当它经过某个矩形的下边时,我们把这个矩形左右覆盖的这一段的点的标记++,我们每次移动时,需要在最终答案上加上当前被标记的点的数量,当我们经过某个矩形的上边时,我们把这一段的标记数量–,扫完后答案就出来了。画画图就可以验证这个方法的正确性,周长也可以用类似的方法解决(还要加一根从左往右的扫描线)。

  • 关于本题线段树:两种方案,一种是维护区间最小值和最小值个数,区间修改时打上 $Lazy$ 标记。这种方案又慢又难处理。另一种方案是根据本题特殊性:每一个 $[l,r]+1$ 都一定对应一个 $[l,r]-1$,所以我们可以直接维护区间内元素整体标记次数和区间内标记的数的总数,后者用 $push_up$ 维护,前者不用管就好。

  • 代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

#define mid ((tree[root].l+tree[root].r)>>1)
#define lc (tree[root].ls)
#define rc (tree[root].rs)

inline int read();

struct node
{
    int l, r, ls, rs;
    int d, num, siz;
} tree[N * 4];

struct Node
{
    int x1, y1, x2, y2;
} Q[N];

struct NODE
{
    int d, wz, type;
    NODE(int a, int b, int c)
    {
        d = a, wz = b, type = c;
    }
    NODE() {}

    bool operator < (const NODE & other ) const
    {
        return d < other.d;
    }
} ls[N * 2];

int n, tot, rt, ys_x[N * 2], ys_y[N * 2];
vector <NODE > ques[N * 2];

void LS()
{
    for(register int k = 1; k <= n; k++)
    {
        ls[k].d = Q[k].x1, ls[k].wz = k, ls[k].type = 1;
        ls[k + n].d = Q[k].x2, ls[k + n].wz = k, ls[k + n].type = 2;
    }
    sort(ls + 1, ls + 1 + 2 * n);
    tot = 0, ls[0].d = -1;
    for(register int k = 1; k <= n * 2; k++)
    {
        if(ls[k].d != ls[k - 1].d) ys_x[++tot] = ls[k].d;
        if(ls[k].type == 1) Q[ls[k].wz].x1 = tot;
        else Q[ls[k].wz].x2 = tot;
    }

    for(register int k = 1; k <= n; k++)
    {
        ls[k].d = Q[k].y1, ls[k].wz = k, ls[k].type = 1;
        ls[k + n].d = Q[k].y2, ls[k + n].wz = k, ls[k + n].type = 2;
    }
    sort(ls + 1, ls + 1 + 2 * n);
    tot = 0, ls[0].d = -1;
    for(register int k = 1; k <= n * 2; k++)
    {
        if(ls[k].d != ls[k - 1].d) ys_y[++tot] = ls[k].d;
        if(ls[k].type == 1) Q[ls[k].wz].y1 = tot;
        else Q[ls[k].wz].y2 = tot;
    }
}

void push_up(int root)
{
    if(tree[root].d) tree[root].num = tree[root].siz;
    else tree[root].num = tree[lc].num + tree[rc].num;
}

void creat(int & root, int l, int r)
{
    root = ++tot, tree[root].siz = ys_y[r] - ys_y[l];
    tree[root].l = l, tree[root].r = r;
    if(l != r - 1)
        creat(lc, l, mid), creat(rc, mid, r);
}

void change(int root, int l, int r, int key)
{
    if(tree[root].l >= l && tree[root].r <= r)
    {
        tree[root].d += key, push_up(root);
        return ;
    }

    if(r <= mid) change(lc, l, r, key);
    else if(l >= mid) change(rc, l, r, key);
    else change(lc, l, mid, key), change(rc, mid, r, key);
    push_up(root);
}

long long query(int root, int l, int r)
{
    if(tree[root].l >= l && tree[root].r <= r)
        return tree[root].num;

    if(r <= mid) return query(lc, l, r);
    else if(l >= mid) return query(rc, l, r);
    else return query(lc, l, mid) + query(rc, mid, r);
}

long long ans;

signed main()
{
    n = read();
    for(register int k = 1; k <= n; k++)
    {
        Q[k].x1 = read(), Q[k].y1 = read();
        Q[k].x2 = read(), Q[k].y2 = read();
    }
    LS(), tot = 0, creat(rt, 1, 2 * n);

    for(register int k = 1; k <= n; k++)
    {
        ques[Q[k].x1].push_back(NODE(Q[k].y1, Q[k].y2, 1));
        ques[Q[k].x2].push_back(NODE(Q[k].y1, Q[k].y2, -1));
    }

    for(register int k = 1; k <= 2 * n; k++)
    {
        ans += query(rt, 1, 2 * n) * (ys_x[k] - ys_x[k - 1]);
        for(int i = 0; i < (int )ques[k].size(); i++)
        {
            int y1 = ques[k][i].d, y2 = ques[k][i].wz, key = ques[k][i].type;
            change(rt, y1, y2, key);
        }
    }

    printf("%lld", ans);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$~\$

$\qquad$ 权值线段树:维护权值上的区间信息的线段树。

$\qquad$ 权值线段树和普通线段树没有本质区别,其本质是线段树维护桶(而不是维护序列),它常用来解决整体第 $K$ 大问题(支持修改,询问整个序列中第 $K$ 大的数是多少)。

$\qquad$ 这个不太好找例题,就不放例题了。

$~\$

$\qquad$ 主席树:即可持久化线段树。

$\qquad$ 从定义上看,主席树可以回溯历史版本…所以我们常用主席树模拟可持久化线性数据结构。但主席树本身一般不用来回溯历史版本,我们常用它来求解静态区间第 $K$ 大问题(权值线段树只能解决整体第 K 大问题)。

$\qquad$ 其具体思路之类的,我的另一篇文章有讲…这里就不赘述了

$~\$

  • 解析:模板题要什么解析。

  • 代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

#define mid ((l+r)>>1)
#define lc (tree[root].ls)
#define rc (tree[root].rs)

inline int read();

struct node
{
    int ls, rs, siz;
} tree[N << 6];

int rt[N], tot, n, m, len, d[N], ys[N];
pair <int , int > P[N];

void creat(int & root, int l, int r)
{
    root = ++tot;
    if(l != r)
        creat(lc, l, mid), creat(rc, mid + 1, r);
}

int update(int root, int l, int r, int key)
{
    int Root = ++tot;
    tree[Root].ls = lc, tree[Root].rs = rc;
    tree[Root].siz = tree[root].siz + 1;
    if(l == r) return Root;

    if(key <= mid)
        tree[Root].ls = update(lc, l, mid, key);
    else
        tree[Root].rs = update(rc, mid + 1, r, key);
    return Root;
}

int query(int Root, int root, int l, int r, int key)
{
    if(l == r) return ys[l];

    int Lc = tree[Root].ls, Size = tree[Lc].siz - tree[lc].siz;
    if(Size >= key) return query(Lc, lc, l, mid, key);
    else return query(tree[Root].rs, rc, mid + 1, r, key - Size);
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        d[k] = read(), P[k] = make_pair(d[k], k);

    sort(P + 1, P + 1 + n), P[0].first = 114514;
    for(register int k = 1; k <= n; k++)
    {
        if(P[k].first != P[k - 1].first)
            ys[++tot] = P[k].first;
        d[P[k].second] = tot;
    }

    len = tot, tot = 0, creat(rt[0], 1, len);
    for(register int k = 1; k <= n; k++)
        rt[k] = update(rt[k - 1], 1, len, d[k]);

    for(register int k = 1; k <= m; k++)
    {
        int l = read(), r = read(), K = read();
        printf("%d\n", query(rt[r], rt[l - 1], 1, len, K));
    }

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$~\$

$~\$

$\qquad$ 主席树可以拓展出不少算法…像可持久化 01-trie 就完全可以按主席树思路来写,可持久化数组和可持久化并查集甚至可以直接用主席树模拟出来。

$\qquad$ Kth 问题还有更进化的版本,比如说区间动态 $Kth$ 这个得拿树套树做…不咋考,这里不复习了。

$\qquad$ 那么就这样吧…线段树一直是热门考点来着,但接下来也要复习其它数据结构了。




前言:

$
$

$\quad\quad$ 本文章主要谈论二分图 & 网络流有关内容,算是一次自我整理吧…

$\quad\quad$ 以下内容参(ban)考(yun)于xht37的博客,和部分二分图 & 网络流资料。


$
$

正文:

$\quad\quad$ 二分图:可化为两关联点集 $A , B$,且 $A , B$ 各自内部无连边的图。

$\quad\quad$ 二分图性质:二分图内无奇环,无奇环的图是二分图。

$\quad\quad$ 二分图判定: $O(n)$ 染色即可。

$
$

  • 解析:没啥好说的,裸题一道。

  • 代码:

  #include <bits/stdc++.h>

  using namespace std;

  inline int read();

  const int N = 1e6 + 10;

  int n, m;

  vector <int > link[N];

  int col[N], flag;

  void dfs(int wz, int color)
  {
      if(flag) return ;

      col[wz] = color;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int to = link[wz][k];
          if(col[wz] == col[to])
              flag = 1;
          if(flag) return ;

          if(!col[to])
              dfs(to, color ^ 1);
      }
  }

  int main()
  {
      while(scanf("%d %d", &n, &m) != EOF)
      {
          flag = 0;
          memset(col, 0, sizeof(col));
          for(register int k = 1; k <= m; k++)
          {
              int u = read(), v = read();
              link[u].push_back(v);
              link[v].push_back(u);
          }

          dfs(1, 2);

          if(!flag) puts("Yes");
          else puts("No");
          memset(link, 0, sizeof(link));
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }



$\quad\quad$ 匹配:在图论中,一个匹配是任意两条边都没有公共定点的边的集合。

$\quad\quad$ 匹配边:对于一个匹配,属于该匹配中的边是匹配边,不属于该匹配中的边是非匹配边。

$\quad\quad$ 匹配点:对于一个匹配,与匹配边有关的点是匹配点,无关的点是非匹配点。

$\quad\quad$ 最大匹配:一个图的所有匹配中,包含匹配边数量最多的匹配。

$\quad\quad$ 例如:

$\quad\quad$ 上图中,${1-2,3-5}$ 是一组匹配,匹配边是 $1-2$ 和 $3-5$,其余的边是非匹配边,匹配点是 $1,2,3,5$,非匹配点是 $4$,最大匹配为:${1-2,3-5}$(不唯一)。

$\quad\quad$ 一般图最大匹配可以用带花树解决,但相当不常见,这里不介绍了、

$
$

$\quad\quad$ 二分图最大匹配(重点):一个无向图图的所有匹配中,包含匹配边数量最多的匹配。

$\quad\quad$ 算法比较多,这里只提最普适的最大流算法:拆点,每个点分为入点和出点,出入点之间连 $1$,把二分图分为左右两部分,左部分入点流 $1$ 连 $S$,右部分出点流 $1$ 连 $E$,把两部分点之间的连边换成左出点连右入点,跑 Dinic。

$\quad\quad$ 实践发现:因为二分图最大匹配中没有额外限制,且某些流具有等价性,所以该图可以不拆点,上述方法等价于:把二分图分为左右两部分,左点流 $1$ 连 $S$,右点流 $1$ 连 $E$,左右点之间按题目所给的连边,直接跑 Dinic。

$
$

  • 代码:
  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, e, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  signed main()
  {
      n = read(), m = read(), e = read(), S = n + m + 1, E = S + 1;
      for(register int k = 1; k <= n; k++)
          add_edge(S, k, 1);
      for(register int k = n + 1; k <= n + m; k++)
          add_edge(k, E, 1);

      for(register int k = 1; k <= e; k++)
      {
          int u = read(), v = read() + n;
          add_edge(u, v, 1);
      }

      Dinic();

      printf("%d", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 二分图最大匹配的要点:模型中的元素可以分为两部分,且所有相关关系集中于这两部分之间,各部分内部元素之间无相关关系。

$
$

  • 解析:找内部没有联系的元素:行,列。我们把行,列看做二分图的两边,如果某一个点可以放下棋子,就在对应行,列之间连边流 $1$,再让起点到每一行,每一列到终点流 $1$ 即可。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 410;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, t, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  bool place[210][210];

  signed main()
  {
      n = read(), m = read(), t = read(), S = n + m + 1, E = S + 1;
      for(register int k = 1; k <= t; k++)
      {
          int x = read(), y = read();
          place[x][y] = 1;
      }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= m; i++)
              if(!place[k][i])
                  add_edge(k, i + n, 1);
      for(register int k = 1; k <= n; k++)
          add_edge(S, k, 1);
      for(register int k = 1; k <= m; k++)
          add_edge(k + n, E, 1);

      Dinic();

      printf("%d", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 完备匹配:所有点都是匹配点的匹配,匹配边数与点数相等。

$\quad\quad$ 多重匹配:在一个点可以被包含在多条边中的条件下进行的匹配。

$\quad\quad$ 解决方案:在二分图上的话,最大流改改就行。

$\quad\quad$ 带权最大匹配:每一条边有一个权值,求一个匹配使得其中所有边的权值和最大(最大匹配即为所有边权值为 $1$ 的带权最大匹配)。

$\quad\quad$ 解决方案:在二分图上的话,把最大流换成费用流就行。

$\quad\quad$ 但是注意到:我们跑费用流求出来匹配一定是一个最大匹配,而带权最大匹配不一定是一个最大匹配,所以直接费用流不能保证跑出带权最大匹配。

$\quad\quad$ 为了解决这个问题,可以新建一个节点,向 $S$ 流 $+\inf$,费用 $0$,向右边所有点流 $1$,费用 $0$,这样一来,我们带权最大匹配就一定是一个最大匹配了。

$
$

$\quad\quad$ 残量网络:对于一种二分图最大匹配,若边 $(x,y)$ 未流满,则连接 $x,y$,构成的网络。

$\quad\quad$ 可行边与必须边(见过,不很常用,不放例题):

  • $\quad$ 可行边:在某些二分图最大匹配的方案中被选上的边。

  • $\quad$ 必须边:在所有二分图最大匹配的方案中都要选的边。

$\quad\quad$ 求法同样分两种情况讨论:

  • $\quad$ 最大匹配是完备匹配:

$\quad\quad\quad$ 把二分图中的非匹配边看作从左部向右部的有向边,匹配边看作从右部向左部的有向边,构成一张新的有向图。

$\quad\quad\quad$ 必须边 :$(x,y)$ 是当前二分图的匹配边,且 $x,y$ 在新的有向图中属于不同的强连通分量。

$\quad\quad\quad$ 可行边 :$(x,y)$ 是当前二分图的匹配边,或 $x,y$ 在新的有向图中属于同一个强连通分量。

  • $\quad$ 最大匹配不一定是完备匹配(普适):

$\quad\quad\quad$ 必须边 :$(x,y)$ 的流量为 $1$,且 $x,y$ 在残量网络上属于不同的强连通分量。

$\quad\quad\quad$ 可行边 :$(x,y)$ 的流量为 $1$,或 $x,y$ 在残量网络上属于同一个强连通分量。

$
$

$
$

$\quad\quad$ 最小点覆盖:在一张图中,所有边至少有一个顶点在一个点集 T中,这样的点集 T 的最少元素个数。

$\quad\quad$ 定理:二分图最小点覆盖等于二分图最大匹配。

$\quad\quad$ 解法:对着二分图,直接跑最大匹配即可。

$\quad\quad$ 要点:二者中必须选一个(一条边连两个点),选了之后另一些元素就不用选了(一个点连着多条边)。

$
$

  • 解析:明确要点,一个任务,要么在这台机器上执行,要么在另一台机器上执行,一台机器开到某个模式后可以执行这个模式下的所有任务,所以把 $A$ 机器的所有模式看做二分图的一边, $B$ 机器的所有模式看做另一边,如果一个任务用 $A_i/B_j$ 模式,就把 $A_i$ 到 $B_j$ 连边,跑最小点覆盖即可,注意:机器一开始就是 $0$ 模式。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 210;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, K, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  void init()
  {
      max_flow = 0, tot = 1;
      S = n + m + 1, E = S + 1;
      memset(link, 0, sizeof(link));
  }

  signed main()
  {
      while(scanf("%d", &n) != EOF && n)
      {
          scanf("%d %d", &m, &K), init();
          for(register int k = 1; k <= K; k++)
          {
              read();
              int u = read() + 1, v = read() + 1;
              add_edge(u, v + n, 1);
          }
          for(register int k = 2; k <= n; k++)
              add_edge(S, k, 1);
          for(register int k = n + 2; k <= n + m; k++)
              add_edge(k, E, 1);
          Dinic();

          printf("%d\n", max_flow);
      }


      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 最小边覆盖:在一张图中,选中一些边,组成 $E$ 集合,使得图中所有点被包含在 $E$ 内,这样的 $E$ 集合内的最少元素个数。

$\quad\quad$ 定理:二分图最小边覆盖等于节点数减最大匹配。

$\quad\quad$ 与最小点覆盖一体两面,用得不多。

$
$

$\quad\quad$ 最大独立集:在一张图中,选出一个点集 $V$,使得集合内的点两两间没有边相连,这样的 $V$ 集合内的最多元素个数。

$\quad\quad$ 定理:二分图最大独立集等于节点数减最大匹配。

$\quad\quad$ 解法:还是对着二分图跑最大匹配。

$\quad\quad$ 要点:某些元素互斥,利用互斥关系连边,最后跑出的最大独立集就是互斥元素的最大数。

$
$

  • 解析: 找要点,各个棋子之间是互斥的,所以套用最大独立集的模型,把能一步到达的位置之间互相连边,最后求出的最大独立集就是答案。从马的走法可以看出,它回到一个点需要 $2/4/6…$ 步,均是偶环,所以该图是二分图,可以利用奇偶关系/染色法把图分成两部分,跑 Dinic 即可。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 4e4 + 10;
  const int M = 5e6 + 10;

  inline int read();

  int n, m, K, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  bool pla[210][210];

  int py[8][2] = {2, 1, -2, 1, 2, -1, -2, -1, 1, -2, 1, 2, -1, 2, -1, -2};

  signed main()
  {
      n = read(), m = read(), S = n * n + 1, E = S + 1;
      for(register int k = 1; k <= m; k++)
      {
          int x = read(), y = read();
          pla[x][y] = 1;
      }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= n; i++)
              if(!pla[k][i])
              {
                  if((k + i) % 2)
                      add_edge(S, (k - 1)*n + i, 1);
                  else
                      add_edge((k - 1)*n + i, E, 1);
              }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= n; i++)
              if(!pla[k][i] && (k + i) % 2)
                  for(int j = 0; j < 8; j++)
                  {
                      int x = k + py[j][0], y = i + py[j][1];
                      if(x > n || x < 1 || y > n || y < 1) continue;
                      if(!pla[x][y]) add_edge((k - 1)*n + i, (x - 1)*n + y, 1);
                  }

      Dinic(), printf("%d", n * n - m - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$
$

$\quad\quad$ 最大团:在一张图中,选出一个点集 $V$,使得集合内的点两两间都有边相连,这样的 $V$ 集合内的最多元素个数。

$\quad\quad$ 定理:无向图(不一定是二分图)的最大团等于其补图的最大独立集。

$\quad\quad$ 解法:求补图,再求最大独立集。

$\quad\quad$ 要点:一般图的最大团是 NPC 的,看到最大团就知道该去找补图了。

$
$

$
$

$\quad\quad$ DAG 最小路径点覆盖:在 DAG 中,用最少的不相交的链覆盖整个 DAG 上的点,问链的最少条数。

$\quad\quad$ 解法:拆点,把一个点拆成$A,B$两个点,按DAG上连边,把每一个$A$点连向其他$B$点,得到二分图,跑最大匹配,最小路径数等于(原)点数减二分图最大匹配数。

$\quad\quad$ 要点:用不交的路径覆盖 DAG。

$
$

  • 解析:本题难点在于输出路径,应该是有复杂度比较优秀的算法的,不过因为网络流自身复杂度比较大,暴力并查集即可。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int fa[N];

  int find(int x)
  {
      return fa[x] == x ? x : fa[x] = find(fa[x]);
  }

  signed main()
  {
      n = read(), m = read(), S = n * 2 + 1, E = S + 1;
      for(register int k = 1; k <= n; k++) fa[k] = k;
      for(register int k = 1; k <= n; k++) add_edge(S, k, 1);
      for(register int k = 1; k <= n; k++) add_edge(k + n, E, 1);

      for(register int k = 1; k <= m; k++)
      {
          int u = read(), v = read();
          add_edge(u, v + n, 1);
      }
      Dinic();

      for(register int k = 1; k <= n; k++)
      {
          for(int i = 0; i < (int )link[k].size(); i++)
          {
              int num = link[k][i], to = edge[num].to;
              if(!edge[num].flow && to - n >= 1 && to - n <= n) fa[find(to - n)] = find(k);
          }
      }

      for(register int k = 1; k <= n; k++)
          if(find(k))
          {
              for(int i = 1; i <= n; i++)
                  if(find(i) == fa[k])
                      printf("%d ", i);
              printf("\n");
              fa[fa[k]] = 0;
          }

      printf("%d", n - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 二分图主要内容差不多就上面那些,以最大匹配为中心,通过最小覆盖,最大独立集/团,路径覆盖 等分支向外延伸,模型很隐蔽,与其它算法结合后,难度相当大。

$\quad\quad$ 下面是网络流的一些知识,网络流个人感觉比较随心所欲,各种建边方法层出不穷,难题要 AC 几乎只能靠感觉,所以下面只提几个比较经典的网络流概念和模型。

$
$

$
$

$\quad\quad$ 网络流:一种特殊的有向图,每条边 $(x,y)$ 有一权值 $c(x,y)$ 表示该边容量,图中(一般)有两特殊点 $S,T$ ,$S$ 是源点, $T$ 是汇点。(这个字母表示和我常用的有差异)

$\quad\quad$ 定义函数 $f(x,y)$ 表示 $x$ 到 $y$ 的实际流量。

$\quad\quad$ 定理:$f(x,y)\le c(x,y)$,$\sum f(u,x)=\sum f(x,v)$,

$\quad\quad$ 即:一条边的实际流量小于该边容量,流入一个点的流等于从这个点流出的流。

$\quad\quad$ 还有一个完善系统的定理: $f(u,v)$ 等价于 $-f(v,u)$(可类比负数)。

$\quad\quad$ 我们称 $\sum f(x,E)$ 为该网络流量。

$\quad\quad$ 当然,我们理解网络流都不是按照上面的定义来的,我们是按照自来水系统来的。

$
$

$\quad\quad$ 最大流/费用流:不写,自己百度去。

$\quad\quad$ :割去后使得源汇点之间不连通的边集。

$\quad\quad$ 最小割(重点):流量最小的一组割。

$\quad\quad$ 定理:最小割等于最大流。

$\quad\quad$ 基础模型:删点/删边 模型

$\quad\quad$ 即对于一张网络,如何删点/边使其不连通。

$\quad\quad$ 删边好说,直接跑最小割就行。删点的话就要看情况处理了。

$
$

  • 题意:求最少删除多少个点,使图不连通(未给出源汇点)。

  • 解析: 显然,对于删点,我们是没办法直接处理的,考虑把一个点的删除转化成一条边上的删除。这种转化常用的方法就是拆点:把一个点拆成出入两个点,之间流 1。注意:可以删的(点转化出的边)流需要的值,不能删的(原边)流无穷大值。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int ls[M], ans;

  signed main()
  {
      while(scanf("%d %d", &n, &m) != EOF)
      {
          tot = 1, ans = n;
          memset(link, 0, sizeof(link));

          for(register int k = 1; k <= n; k++)
              add_edge(k, k + n, 1);

          for(register int k = 1; k <= m; k++)
          {
              int u = read() + 1, v = read() + 1;
              add_edge(u + n, v, 0x3f3f3f3f);
              add_edge(v + n, u, 0x3f3f3f3f);
          }

          for(register int k = 1; k <= tot; k++)
              ls[k] = edge[k].flow;

          for(register int k = 1; k <= n; k++)
              for(int i = k + 1; i <= n; i++)
              {
                  max_flow = 0;
                  for(int j = 1; j <= tot; j++)
                      edge[j].flow = ls[j];
                  S = k + n, E = i, Dinic();
                  ans = min(ans, max_flow);
              }

          printf("%d\n", ans);
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 进阶模型: 集合划分模型

$\quad\quad$ 即有多个元素,求把它们划分成两类的最优方案。

$\quad\quad$ 一种常见的题目是:给定每个元素划分成两类的不同代价,加上限制条件 $w(x,y)$ 表示 $x,y$ 不在同一个类别中需要额外付出的代价,求最小代价。

$\quad\quad$ 解决方式是:建 $S,E$ 代表两类,对每一个元素向 $S,E$ 连流为代价的边,限制 $w(x,y)$ 转化成 $x,y$ 两点间的流 $w$ 双向边,跑最小割即可。

$
$

  • 解析:在确定本题可以最小割求解后,思路就很显然了。抓要点:把人分成睡觉和不睡觉两类,不妨把睡觉设为 $S$,不睡觉设为 $E$ ,对每个人,向意愿的一侧流 0(不连边),不愿的一侧流 1,好朋友之间流 1,跑最小割即可。

  • 代码:

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 1e3;
  const int M = 1e6;

  int S, E, tot = 1, max_flow, n, m;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int c)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  queue <int > q;
  int deep[N], cur[N];

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      q.push(S), deep[S] = 0;

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(edge[num].flow && deep[to] > deep[wz] + 1)
                  deep[to] = deep[wz] + 1, q.push(to);
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;

          if(edge[num].flow && deep[to] == deep[wz] + 1 && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;
          if(used == flow) break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  signed main()
  {
      n = read(), m = read(), S = n + 1, E = S + 1;
      for(register int k = 1; k <= n; k++)
      {
          int x = read();
          if(x == 0) add_edge(S, k, 1);
          else add_edge(k, E, 1);
      }

      for(register int k = 1; k <= m; k++)
      {
          int u = read(), v = read();
          add_edge(u, v, 1);
          add_edge(v, u, 1);
      }

      Dinic(), printf("%d\n", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$
$

$\quad\quad$ 特殊模型:平面图最小割

$\quad\quad$ 平面图:边与边只在定点相交的图(除顶点外无交点/交点都是顶点/平面被各条边分为互不相交的区域)。

$\quad\quad$ 平面图的对偶图:把平面图每一块区域当做点,若平面图中两块区域有交边就将其连边,得到的图是该平面图对偶图。

$\quad\quad$ 细节:连边的边权等于公共边的流量,把源点和汇点在不穿过其他边的前提下相连,得到的区域代表起点区域,剩下的区域代表终点区域。

$\quad\quad$ 定理:平面图最大流=平面图最小割=对偶图最短路。

$
$

  • 解析:显然,以左上角点为源点,右下角点为汇点,我们要求的就是平面图最小割,直接转化成对偶图最短路即可。

  • 代码(懒得优化,需要吸氧):

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 3e6;
  typedef pair <int , int > P;
  #define mp make_pair

  struct node
  {
      int to, len;
      node (int a, int b)
      {
          to = a, len = b;
      }
      node () { }
  };
  vector <node > link[N];

  void add_edge(int u, int v, int w)
  {
      link[u].push_back(node(v, w));
      link[v].push_back(node(u, w));
  }

  int n, m, S, E;

  int dis[N], sol[N];

  priority_queue <P, vector <P> , greater<P> > q;

  void dij()
  {
      memset(dis, 0x3f, sizeof(dis));
      q.push(mp(0, S)), dis[S] = 0;

      while(!q.empty())
      {
          int wz = q.top().second;
          q.pop();

          if(sol[wz]) continue;
          sol[wz] = 1;

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int to = link[wz][k].to, len = link[wz][k].len;
              if(dis[to] > dis[wz] + len)
              {
                  dis[to] = dis[wz] + len;
                  q.push(mp(dis[to], to));
              }
          }
      }

      printf("%d\n", dis[E]);
  }

  signed main()
  {
      n = read() - 1, m = read() - 1, S = n * m * 2 + 1, E = S + 1;
      for(register int k = 0; k <= n; k++)
          for(int i = 1; i <= m; i++)
          {
              if(k == 0) add_edge(i * 2, E, read());
              else if(k == n) add_edge((n - 1)*m * 2 + i * 2 - 1, S, read());
              else add_edge(k * m * 2 + i * 2, (k - 1)*m * 2 + i * 2 - 1, read());
          }
      for(register int k = 1; k <= n; k++)
          for(int i = 0; i <= m; i++)
          {
              if(i == 0) add_edge(S, (k - 1)*m * 2 + 1, read());
              else if(i == m) add_edge(E, k * m * 2, read());
              else add_edge((k - 1)*m * 2 + i * 2 + 1, (k - 1)*m * 2 + i * 2, read());
          }
      for(register int k = 1; k <= n; k++)
          for(register int i = 1; i <= m; i++)
              add_edge((k - 1)*m * 2 + i * 2, (k - 1)*m * 2 + i * 2 - 1, read());

      dij();

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }


$\quad\quad$ 引申模型:最大权闭合子图:给定 $n$ 个元素,每个元素有一个价值 $v_i$ ,元素之间有限制关系 $w(x,y)$ 表示选了 $x$ 才能选 $y$,求最大价值。

$\quad\quad$ 解法:对于所有元素,若其权值为正,向源点流 $v_i$,否则向汇点流 $-v_i$,对于 $w(x,y)$,从 $x$ 流 $\inf$ 到 $y$,跑出最小割,答案为原正权和-最小割。

$\quad\quad$ 要点:先 XX 才能 XX,要求无选择个数限制(否则就尝试树形DP吧)。

$
$

  • 解析:几乎是板子,最后要求输出方案,方案就是最后与 $S$ 连通的实验和仪器,证明略过,可以自行百度。
  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <iostream>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 1e3;
  const int M = 1e6;

  int S, E, tot = 1, max_flow, n, m;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int c)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  queue <int > q;
  int deep[N], cur[N];

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      q.push(S), deep[S] = 0;

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(edge[num].flow && deep[to] > deep[wz] + 1)
                  deep[to] = deep[wz] + 1, q.push(to);
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;

          if(edge[num].flow && deep[to] == deep[wz] + 1 && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;
          if(used == flow) break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int answ;

  signed main()
  {
      m = read(), n = read(), S = m + n + 1, E = S + 1;
      for(register int k = 1; k <= m; k++)
      {
          int x = read();
          add_edge(S, k, x), answ += x;

          char tools[10000];
          memset(tools, 0, sizeof tools);
          cin.getline(tools, 10000);
          int ulen = 0, tool;
          while (sscanf(tools + ulen, "%d", &tool) == 1)
          {
              add_edge(k, tool + m, 0x3f3f3f3f);

              if (tool == 0)
                  ulen++;
              else
              {
                  while (tool)
                  {
                      tool /= 10;
                      ulen++;
                  }
              }
              ulen++;
          }
      }

      for(register int k = 1; k <= n; k++)
          add_edge(k + m, E, read());
      Dinic();

      for(register int k = 1; k <= m; k++)
          if(deep[k] != 0x3f3f3f3f)
              printf("%d ", k);
      puts("");

      for(register int k = m + 1; k <= m + n; k++)
          if(deep[k] != 0x3f3f3f3f)
              printf("%d ", k - m);
      puts("");

      printf("%d\n", answ - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 好像还剩上下界网络流的知识点来着…懒得写了。

$\quad\quad$ 费用流基本上就没啥板子了,得对题下算法......

$\quad\quad$ 稍微放一道简单的例题吧。

$
$

  • 解析: 没啥难度,拆点后稍微连一下跑费用流就行了。

  • 代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

inline int read();

const int N = 1e4;
const int M = 5e6;

int S, E, tot = 1, max_flow, min_cost, n, m;

struct node
{
    int to, flow, cost;
} edge[M];
vector <int > link[N];

void add_edge(int u, int v, int c, int w)
{
    link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c, edge[tot].cost = w;
    link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0, edge[tot].cost = -w;
}

queue <int > q;
int dis[N], in[N];

bool SPFA()
{
    memset(in, 0, sizeof(in));
    memset(dis, 0xef, sizeof(dis));
    q.push(S), dis[S] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = 0;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int num = link[wz][k], to = edge[num].to, len = edge[num].cost;
            if(edge[num].flow && dis[to] < dis[wz] + len)
            {
                dis[to] = dis[wz] + len;
                if(!in[to]) in[to] = 1, q.push(to);
            }
        }
    }

    return dis[E] != 0xefefefef;
}

int dfs(int wz, int flow)
{
    if(wz == E)
    {
        max_flow += flow;
        return flow;
    }

    in[wz] = 1;
    int used = 0;

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int num = link[wz][k], to = edge[num].to, len = edge[num].cost, Flow;

        if(!in[to] && edge[num].flow && dis[to] == dis[wz] + len && (Flow = dfs(to, min(flow - used, edge[num].flow))))
            edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, min_cost += Flow * len, used += Flow;
        if(used == flow) break;
    }

    in[wz] = 0;
    return used;
}

void Dinic()
{
    while(SPFA())
        dfs(S, 0x3f3f3f3f);
}

int py[2][2] = {0, 1, 1, 0};

signed main()
{
    n = read(), m = read(), S = n * n * 2 + 1, E = S + 1;
    add_edge(S, 1, m, 0), add_edge(n * n * 2, E, m, 0);
    for(register int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
        {
            add_edge((k - 1)*n + i, (k - 1)*n + i + n * n, 0x3f3f3f3f, 0);
            add_edge((k - 1)*n + i, (k - 1)*n + i + n * n, 1, read());
        }

    for(register int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 2; j++)
            {
                int x = k + py[j][0], y = i + py[j][1];
                if(x >= 1 && x <= n && y >= 1 && y <= n)
                    add_edge((k - 1)*n + i + n * n, (x - 1)*n + y, 0x3f3f3f3f, 0);
            }

    Dinic(), printf("%d\n", min_cost);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}


$
$

结语:

$\quad\quad$ 上下界可行流咕掉了。




Sata_星空
3个月前

前言:

$
$

$\quad\quad$ 图片咕了可以去 洛谷博客 看。

$\quad\quad$ 最近复习了一下主席树,然后刷了刷主席树的训练场。

$\quad\quad$ 刷了第一题后发现不会做第二题:P3157 [CQOI2011]动态逆序对

$\quad\quad$ 翻了翻题解,发现这题要求写一个带修的主席树…

$\quad\quad$ 看了半天,云里雾里,还以为是什么神奇的算法…

$\quad\quad$ 结果突然就发现:这玩意不是树套树么?

$\quad\quad$ AC 后写下本文加以巩固。


$
$

正文:

$
$

$\quad\quad$ 在介绍树状数组套动态开点线段树之前,我先大致提一提主席树。

$\quad\quad$ 主席树,顾名思义,就是某 hjt 提出的树。(雾

$\quad\quad$ 其学名为可持久化线段树,一般也可指动态开点线段树。

$\quad\quad$ 主要用来解决需要维护序列中某一段关于值的信息的题目。

$\quad\quad$ 什么叫 需要维护序列中某一段关于值的信息的题目 ?

$\quad\quad$ 众所周知,查询与值域有关的题目,有时可以用权值线段树解决。

$\quad\quad$ 比如说:查询整个序列中的 $\operatorname{Kth}$。

$\quad\quad$ 又众所周知:查询与原序列中的某个区间有关的题目,若是维护的数组具有可减性,就可以使前缀和解决。

$\quad\quad$ 比如说:查询区间 $[L,R]$ 内的所有数的和。

$\quad\quad$ 而把这两种题目合并起来,就成了 需要维护序列中某一段关于值的信息的题目 了。

$\quad\quad$ 比如说:查询区间 $[L,R]$ 内的 $\operatorname{Kth}$。

$\quad\quad$ 既然题目可以合并为一个,那么我们的算法是否也可以合并为一个?

$\quad\quad$ 答案是肯定的,我们可以开 $n$ 棵权值线段树,分别维护区间 $[1,1],[1,2],[1,3]......[1,n]$ 内的信息,查询时,我们利用信息的可减性即可求出答案。

$\quad\quad$ 但是 $\operatorname{Kth}$ 显然是不具有可减性的,所以我们不可能直接维护 $\operatorname{Kth}$。

$\quad\quad$ 我们可以维护 $size$(权值线段树中某一段区间内有多少个元素) 信息,而 $size$ 显然是具有可减性的。

$\quad\quad$ 这里举个栗子(黑色数字代表当前线段的维护值域区间,有颜色的数字代表当前区间的元素个数(size)):

$\quad\quad$ 我们提取出维护 $[1,L-1]$ 区间信息的权值线段树(假设是左边这颗),提取出维护 $[1,R]$ 区间信息的权值线段树(右边这棵)。

$\quad\quad$ 我们把这两颗线段树的每一个区间中 $size$ 的值对应相减,就得到了一颗维护 $[L,R]$ 区间信息的权值线段树。

$\quad\quad$ 然后我们就可以在新的这颗线段树中简单的查找 $\operatorname {Kth}$了。

$\quad\quad$ 然而,虽然这个算法查询的时间复杂度是优秀的 $O(logn)$,但其空间复杂度以及建树时间复杂度达到了 $O(n^2)$(开了 $n$ 棵权值线段树),显然无法承受。

$\quad\quad$ 主席树就是在上面方法的基础上,对其空间复杂度进行优化而产生的数据结构。

$
$


$
$

$\quad\quad$ 如何优化空间复杂度?我们比较维护 $[1,x-1]$ 区间的权值线段树和维护 $[1,x]$ 区间的权值线段树(以下面两棵树为例,假设插入的值为 $1$)。

$\quad\quad$ 不难发现,插入新元素前的线段树与插入后的线段树仅仅只有一条链上的节点有区别,即 $logn$ 个节点有区别。

$\quad\quad$ 那我们为什么还要重复建立那些没有改变的节点?直接把原有树的该节点 “递” 给新树不就行了?

$\quad\quad$ 就像这样(绿色/棕红色的边代表线段树中的父子关系):

$\quad\quad$ 显然,这样操作后,任然可以从两颗线段树的根节点开始,顺着儿子访问这棵完整的线段树,但因为两棵树共用了一部分区域的关系,新建树的节点数仅仅只有改变了的 $logn$,因此,这样处理后,该数据结构的空间复杂度仅 $O(n+(n-1)logn)=O(nlogn)$。

$\quad\quad$ 这玩意就是所谓的主席树,即可持久化线段树。

$\quad\quad$ 为什么说它可持久化?因为如果我们对于任意的一次修改,新建修改路径上的所有节点,并按照上述方式建边,那么,我们就可以以 $O(nlogn)$ 的空间代价保存所有的历史状态,甚至回退到某一历史状态。

$\quad\quad$ 这里放一下板子和代码,然后就可以预备进入正题了。

$\quad\quad$ 板子:P3834 【模板】可持久化线段树 1(主席树)。

$\quad\quad$ 代码:

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, ch = '~';

    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x;
}

const int N = 200010;
const int M = N << 5;

int n, m, cnt, tot;
int d[N], ys[N], Root[N];
pair <int , int > a[N];

#define mid ((l+r)>>1)
#define ls (tree[root].lc)
#define rs (tree[root].rc)

struct node
{
    int lc, rc;
    int size;
} tree[M];

void creat(int & root, int l, int r)
{
    root = ++tot;
    if(l != r) creat(ls, l, mid), creat(rs, mid + 1, r);
}

int update(int pre, int l, int r, int x)
{
    int root = ++tot;

    ls = tree[pre].lc, rs = tree[pre].rc, tree[root].size = tree[pre].size + 1;

    if(l == r) return root;

    if(x <= mid) ls = update(tree[pre].lc, l, mid, x);
    else rs = update(tree[pre].rc, mid + 1, r, x);

    return root;
}

int Kth(int root1, int root2, int l, int r, int rank)
{
    if(l == r) return ys[l];

    int x = tree[tree[root2].lc].size - tree[tree[root1].lc].size;
    if(rank <= x) return Kth(tree[root1].lc, tree[root2].lc, l, mid, rank);
    else return Kth(tree[root1].rc, tree[root2].rc, mid + 1, r, rank - x);
}

int main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        a[k] = make_pair(read(), k);

    sort(a + 1, a + 1 + n);
    for(register int k = 1; k <= n; k++)
    {
        if(a[k].first != a[k - 1].first || k == 1)
            ys[++cnt] = a[k].first;
        d[a[k].second] = cnt;
    }

    creat(Root[0], 1, cnt);
    for(register int k = 1; k <= n; k++)
        Root[k] = update(Root[k - 1], 1, cnt, d[k]);

    for(register int k = 1; k <= m; k++)
    {
        int l = read(), r = read(), x = read();
        printf("%d\n", Kth(Root[l - 1], Root[r], 1, cnt, x));
    }

    return 0;
}

$
$

$
$


$
$

$\quad\quad$ 下面进入正题。

$\quad\quad$ 我们知道,静态区间 $\operatorname{Kth}$ 可以用主席树维护解决,那么动态的区间 $\operatorname{Kth}$ 怎么解决呢?

$\quad\quad$ 比如说这道题:P2617 Dynamic Rankings

$\quad\quad$ 题意很简单:维护一种数据结构,支持单点修改,区间 $\operatorname{Kth}$。

$\quad\quad$ 能否直接上主席树暴力修改?

$\quad\quad$ 众所周知,主席树本质上维护的是前缀和信息,如果我们要修改 $i$ 处的点值,我们就要修改 $i - n$ 中每一棵权值线段树内的信息,而每一棵权值线段树都有 $log$ 个节点需要修改,所以我们单次修改的复杂度会达到恐怖的 $O(nlogn)$。

$\quad\quad$ 当然,我们在主席树中是共用了一些点的,所以对于某些点的修改可能会重复,我们可以把那些已修改的节点打上标记,再次访问到它的时候就不用修改了。

$\quad\quad$ 这似乎可以降低暴力修改的时间复杂度,但因为 $n$ 棵树中,每一棵树的根节点都是新建的,而我们对于每一棵树的修改一定会从根节点开始,所以我们每次修改都会至少修改 $n$ 个节点(各棵树的根节点),单次修改复杂度下界也还是 $O(n)$。

$\quad\quad$ 因此,暴力不可接受。

$\quad\quad$ 如何对暴力进行优化?我们把问题简化考虑。

$\quad\quad$ 假设我们要维护的信息与值域无关,也就是说我们不用维护权值线段树,那么我们应该怎么做?

$\quad\quad$ 比如说题目简化为这样:维护一种数据结构,支持单点修改,区间 $\operatorname{Sum}$。

$\quad\quad$ 我们原先的暴力主席树,类比过来就相当于跑了一个前缀和。

$\quad\quad$ 但是单点修改区间求值为啥要跑前缀和?树状数组跑一下不就完了吗?

$\quad\quad$ 使用树状数组,显然可以把前缀和的 $O(n)$ 修改, $O(1)$ 查询优化到 $O(logn)$ 修改和查询。

$\quad\quad$ 对于更复杂一些的本题是否也是如此?

$\quad\quad$ 如果用树状数组代替前缀和维护权值线段树(主席树本质上就是用前缀和维护权值线段树),我们是否可以把之前的 $O(nlogn)$ 修改,$O(logn)$ 查询,优化到 $O(nlog^2n)$ 修改和查询?

$\quad\quad$ 显然是可以的。

$\quad\quad$ 具体而言如何实现?

$\quad\quad$ 我们考虑树状数组是怎么实现单点修改,区间查询的(下面介绍的很简略,但要是你连树状数组都不会,你看树套树干嘛):

$\quad\quad$ 树状数组构造时,建立了 $n$ 个节点,分别维护$[1,1],[1,2],[3,3],[1,4]…[n-lowbit(n)+1,n]$ 区间内信息。

$\quad\quad$ 修改时,修改 $x,x+lowbit(x)......$ 等节点,直到达到 $n$ 之外。

$\quad\quad$ 查询时,分别查询 $[1,l-1]$ 和 $[1,r]$ 内的信息,然后相减。

$\quad\quad$ 类比到树套树上,就是构造 $n$ 棵权值线段树,分别维护 $[1,1],[1,2],[3,3],[1,4]…[n-lowbit(n)+1,n]$ 区间内信息。

$\quad\quad$ 修改时,修改以 $x,x+lowbit(x)......$ 等节点为根的权值线段树,直到达到 $n$ 之外。

$\quad\quad$ 查询时,分别构造 $[1,l-1]$ 和 $[1,r]$ 的权值线段树,然后相减得到 $[l,r]$ 的权值线段树。

$\quad\quad$ 其实,这里的操作只不过是把树状数组中的 “节点” 换成了 “权值线段树” 而已,了解思路之后自己就可以口胡出来。

$\quad\quad$ 下面放一下上面那例题 P2617 Dynamic Rankings 的代码:

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))

using namespace std;

inline int read()
{
    int x = 0, ch = '~', fh = 1;

    while(!isdigit(ch)) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

const int N = 200010;

int a[N], ys[N], Root[N];
int n, m , num, tot, cnt;

struct Node
{
    int opt, a, b, c;
} ques[N];
struct NODE
{
    int type, wz, key;

    bool operator < (const NODE & other) const
    {
        return key < other.key;
    }
} cl[N * 2];

struct node
{
    int lc, rc, size;
} tree[N << 6];

#define mid ((l+r)>>1)
#define ls (tree[root].lc)
#define rs (tree[root].rc)

void update(int & root, int l, int r, int key, int val)
{
    if(!root) root = ++tot;
    tree[root].size += val;

    if(l == r) return ;
    if(key <= mid) update(ls, l, mid, key, val);
    else update(rs, mid + 1, r, key, val);
}

void Change(int wz, int key, int val)
{
    for(int k = wz; k <= n; k += lowbit(k))
        update(Root[k], 1, cnt, key, val);
}

vector <int > L, R;

int query(int l, int r, int Kth)
{
    if(l == r) return ys[l];

    int l_sum = 0, r_sum = 0;
    for(int k = 0; k < (int )L.size(); k++) l_sum += tree[tree[L[k]].lc].size;
    for(int k = 0; k < (int )R.size(); k++) r_sum += tree[tree[R[k]].lc].size;

    int Size = r_sum - l_sum;
    if(Kth <= Size)
    {
        for(int k = 0; k < (int )L.size(); k++) L[k] = tree[L[k]].lc;
        for(int k = 0; k < (int )R.size(); k++) R[k] = tree[R[k]].lc;
        return query(l, mid, Kth);
    }
    else
    {
        for(int k = 0; k < (int )L.size(); k++) L[k] = tree[L[k]].rc;
        for(int k = 0; k < (int )R.size(); k++) R[k] = tree[R[k]].rc;
        return query(mid + 1, r, Kth - Size);
    }
}

int Query(int l, int r, int Kth)
{
    L.clear(), R.clear();
    for(int k = l; k > 0; k -= lowbit(k)) L.push_back(Root[k]);
    for(int k = r; k > 0; k -= lowbit(k)) R.push_back(Root[k]);
    return query(1, cnt, Kth);
}

int main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        a[k] = read(), cl[++num].type = 1, cl[num].wz = k, cl[num].key = a[k];
    for(register int k = 1; k <= m; k++)
    {
        char opt[2];
        scanf("%s", opt);

        if(opt[0] == 'Q') ques[k].opt = 0, ques[k].a = read(), ques[k].b = read(), ques[k].c = read();
        else
        {
            ques[k].opt = 1, ques[k].a = read(), ques[k].b = read();
            cl[++num].type = 2, cl[num].wz = k, cl[num].key = ques[k].b;
        }
    }

    sort(cl + 1, cl + 1 + num);
    int last = 0xefefefef;
    for(register int k = 1; k <= num; k++)
    {
        if(cl[k].key != last)
            last = cl[k].key, cnt++, ys[cnt] = cl[k].key;
        if(cl[k].type == 1) a[cl[k].wz] = cnt;
        else ques[cl[k].wz].b = cnt;
    }

    for(register int k = 1; k <= n; k++)
        Change(k, a[k], 1);

    for(register int k = 1; k <= m; k++)
    {
        if(ques[k].opt)
        {
            Change(ques[k].a, a[ques[k].a], -1);
            a[ques[k].a] = ques[k].b;
            Change(ques[k].a, a[ques[k].a], 1);
        }
        else
            printf("%d\n", Query(ques[k].a - 1, ques[k].b, ques[k].c));
    }

    return 0;
}

$\quad\quad$ 上面提到,主席树是用来解决需要维护序列中某一段关于值的信息的题目的东西。

$\quad\quad$ 而树状数组套动态开点线段树就是用来解决需要维护序列中某一段关于值的信息并支持修改的题目的东西了。

$\quad\quad$ (有的人说这是树状数组套主席树,我觉得这么说是很不科学的,毕竟主席树本身就是用前缀和维护的权值线段树,而这里是用树状数组维护权值线段树,把它称作树状数组套线段树才对吧,或者说是带修主席树也说得过去......不过话说回来,主席树 到底是指啥,本身也是有争议的吧,要是把它理解为动态开点线段树,貌似说这个树套树是树状数组套主席树也没错)

$\quad\quad$ 再一道练习:P3157 [CQOI2011]动态逆序对

$\quad\quad$ 代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

inline int read()
{
    int x = 0, ch = '~', fh = 1;

    while(!isdigit(ch)) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

long long ans;
int n, m, tot;
int a[N], wz[N], Root[N];

struct node
{
    int lc, rc, size;
} tree[N << 6];

#define ls (tree[root].lc)
#define rs (tree[root].rc)
#define mid ((l + r) >> 1)
#define lowbit(x) (x & (-x))

void update(int & root, int l, int r, int key, int val)
{
    if(!root) root = ++tot;
    tree[root].size += val;

    if(l == r) return ;
    if(key <= mid) update(ls, l, mid, key, val);
    else update(rs, mid + 1, r, key, val);
}

void Change(int wz, int key, int val)
{
    for(int k = wz; k <= n; k += lowbit(k))
        update(Root[k], 1, n, key, val);
}

vector <int > L, R;

int query(int l, int r, int x)
{
    if(x <= mid)
    {
        if(l == r) return 0;

        for(int k = 0; k < (int )L.size(); k++) L[k] = tree[L[k]].lc;
        for(int k = 0; k < (int )R.size(); k++) R[k] = tree[R[k]].lc;
        return query(l, mid, x);
    }
    if(l == r)
    {
        int l_size = 0, r_size = 0;
        for(int k = 0; k < (int )L.size(); k++) l_size += tree[L[k]].size;
        for(int k = 0; k < (int )R.size(); k++) r_size += tree[R[k]].size;
        return r_size - l_size;
    }

    int l_size = 0, r_size = 0;
    for(int k = 0; k < (int )L.size(); k++) l_size += tree[tree[L[k]].lc].size;
    for(int k = 0; k < (int )R.size(); k++) r_size += tree[tree[R[k]].lc].size;
    for(int k = 0; k < (int )L.size(); k++) L[k] = tree[L[k]].rc;
    for(int k = 0; k < (int )R.size(); k++) R[k] = tree[R[k]].rc;
    return r_size - l_size + query(mid + 1, r, x);
}

int Query(int l, int r, int x)
{
    L.clear(), R.clear();
    for(int k = l; k > 0; k -= lowbit(k)) L.push_back(Root[k]);
    for(int k = r; k > 0; k -= lowbit(k)) R.push_back(Root[k]);
    return query(1, n, x);
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
    {
        a[k] = read(), wz[a[k]] = k;
        if(k > 1) ans += k - 1 - Query(0, k - 1, a[k]);
        Change(k, a[k], 1);
    }

    for(register int k = 1; k <= m; k++)
    {
        printf("%lld\n", ans);

        int x = read();
        Change(wz[x], x, -1);
        ans -= Query(wz[x], n, x);
        ans -= Query(0, wz[x] - 1, 0x3f3f3f3f) - Query(0, wz[x] - 1, x);
    }

    return 0;
}

$
$


结语:

$\quad\quad$ 个人感觉树套树的结构并没有什么条条框框,大多数时候都是靠自己口胡来着。

$\quad\quad$ 到这里还记模板貌似没啥大用啊…要是你记了个树状数组套动态开点线段树,哪天考一个线段树套平衡树,那不就 GG 了么......

$
$




Sata_星空
4个月前

原文有发在洛谷上,如果图片咕掉了可以去翻一翻那篇博文

前言:

$
$

$\quad\quad$ 不得不说,树真是一种神奇的数据结构呢。

$\quad\quad$ 即使是在图论的某些经典问题中,也可以看到它的身影。

$\quad\quad$ 比如说:解决最短路问题的最短路树。

$\quad\quad$ 比如说:解决瓶颈路问题的克鲁斯卡尔重构树。

$\quad\quad$ 以及下面要介绍的:解决最小割问题的最小割树。

$\quad\quad$ 什么?你说你完全没听说过上面那三个玩意?

$
$

$\quad$ 前置芝士:

  • $\quad\quad$ 最大流算法(至少要会Dinic)

  • $\quad\quad$ 最小割的概念与最小割最大流定理(最小割等于最大流)

  • $\quad\quad$ 树上倍增基础(这个应该都会吧)

  • $\quad\quad$ 简单的分治思想(提高组水平的样子)

$
$

$\quad$ 注:本文为了便于理解,并没有使用标准的数学语言进行表达和证明。


$
$

目录:

$\quad\quad$ $1-1:$ 问题引入

$\quad\quad$ $1-2:$ 问题探究

$\quad\quad$ $2-2:$ 定理证明

$\quad\quad$ $2-1:$ 引理证明

$\quad\quad$ $3-1:$ 最小割树定义

$\quad\quad$ $3-2:$ 最小割树构建

$\quad\quad$ $3-3:$ 最小割树性质

$\quad\quad$ $4:$ 代码与练习


$
$

正文:

$
$

$\quad$ $1-1:$问题引入:给定一张$n$个点,$m$条边的无向图,求 任意两点间 的最小割。

$\quad\quad$ 题意很显然,以下图为例,就是求(1,2)之间,(1,3)之间,(1,4)之间,(2,3)之间,(2,4)之间,(3,4)之间的最小割。

$\quad\quad$

$\quad\quad$ 也就是说,我们要求 $\frac{n*(n-1)}{2}$ 组最小割。

$
$

$\quad$ $1-2:$问题探究:

$\quad\quad$ 本题朴素做法是跑 $\frac{n(n-1)}{2}$ 遍 Dinic,复杂度是 $O(n^2mn^2)=O(n^4m)$。

$\quad\quad$ 即使最大流算法的复杂度很难达到上界,这个复杂度也显然不可接受。

$\quad\quad$ 能否获得更优的复杂度?(当然可以,不然我写这个干嘛)

$\quad\quad$ 对我们的复杂度进行分析:前面的 $O(n^2m)$ 是Dinic的复杂度,存在优化空间,但不大(ISAP/HLPP 并不比 Dinic 快特别多)。

$\quad\quad$ 后面的 $O(n^2)$ 是枚举点对的复杂度,我们考虑对这一部分进行优化。

$\quad\quad$ 如果我们打表观察上图各个点之间的最小割的数值(如下图)。

$P_1$ $P_2$ $P_3$ $P_4$
$P_1$ 0 3 3 3
$P_2$ 3 0 4 4
$P_3$ 3 4 0 4
$P_4$ 3 4 4 0

$\quad\quad$ 我们会发现,表中仅有 $3,4$ 两个数。

$\quad\quad$ 是否能够猜想:对于一张 $n$ 个点的图来说,点对间最小割的数值其实远小于 $n^2$ 种?

$\quad\quad$ 这就涉及到了一个定理:给定一张 $n$ 个点的无向图,最多只有 $n-1$ 种本质不同(也可理解成值不同)的最小割。

$\quad\quad$ 如何证明这个定理?(当然是归纳法呐

$\quad\quad$ 又如何利用该定理优化算法复杂度?

$
$


$
$

$\quad$ $2-1:$定理证明(建议跳过):

$\quad\quad$ 定理表述:给定一张 $n$ 个点的无向图,最多只有 $n-1$ 种本质不同的最小割。

$\quad\quad$ 以下图为例加以证明:

$\quad\quad$ 我们令 $\operatorname{Cut}(A,B)$ 表示在原图内 $A,B$ 之间最小割所包含边的集合(在公式中出现时表示这些边的权值和)。

$\quad\quad$ 注意:$\operatorname{Cut}(A,B)$ 在本文的任何地方,
都代表 原图 中 $A,B$ 之间的最小割所包含的边集。

$\quad\quad$ 显然, 割去 $\operatorname{Cut}(A,B)$ 后,整张图分成两个联通部分,就像下面这样:

$\quad\quad$ 根据引理三(引理表述及证明在定理的后面),对于 $A$ 所在连通块中的任一点 $X$,都有 $\operatorname{Cut}(B,X) = \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,X))$。

$\quad\quad$ 我们不妨再尝试在原图中割掉 $\operatorname{Cut}(A,C)$。

$\quad\quad$ 同样根据引理三,对于 $C$ 所在连通块中的任一点 $Y$,都有 $\operatorname{Cut}(A,Y) = \min(\operatorname{Cut}(A,C),\operatorname{Cut}(C,Y))$。

$\quad\quad$ 看出什么了吗?如果把这里的 $Y$ 和之前的 $X$ 取为同一个点(当然,要求这个点同时满足上面两式中 $X$ 与 $Y$ 所满足的的条件),就可以把这两个式子整合成一个式子。

$\quad\quad$ 比如说,取 $X=Y=G$,有$\operatorname{Cut}(B,G) = \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,G))$,$\operatorname{Cut}(A,G) = \min(\operatorname{Cut}(A,C),\operatorname{Cut}(C,G))$。

$\quad\quad$ 带入得$\operatorname{Cut}(B,G) = \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C),\operatorname{Cut}(C,G))$。

$\quad\quad$ 我们不妨再尝试分别割掉 $\operatorname{Cut}(C,G)$ 和 $\operatorname{Cut}(F,G)$,看看还会得到哪些式子。

$\quad\quad$ 这里列举割去上述几组 $cut$ 并进行转化后,只关于 $A,C,G,F$ 四点的式子:

$\quad\quad$ $\operatorname{Cut}(A,C),\operatorname{Cut}(C,G),\operatorname{Cut}(F,G)$

$\quad\quad$ $\operatorname{Cut}(A,G) = \min(\operatorname{Cut}(A,C),\operatorname{Cut}(C,G))$

$\quad\quad$ $\operatorname{Cut}(A,F) = \min(\operatorname{Cut}(A,C),\operatorname{Cut}(C,G),\operatorname{Cut}(G,F))$

$\quad\quad$ $\operatorname{Cut}(C,F) = \min(\operatorname{Cut}(C,G),\operatorname{Cut}(G,F))$

$\quad\quad$ 至此,我们可以看出,给出一些诸如 $\operatorname{Cut}(A,C),\operatorname{Cut}(C,G),\operatorname{Cut}(G,F)$之类的“单位元”,我们就可以表示出 $A,C,G,F$ 中任意两点间的最小割。

$\quad\quad$ 这些“单位元”到底是什么?很容易看出来,这些“单位元”就是我们所割去的边集。

$\quad\quad$ 当然,我们不是任意割边的,这里割边要求其实与最小割树构造时的割边要求是相同的。

$\quad\quad$ 也就是说,我们所选择割掉的 $Cut(X,Y)$ 中的 $X$ 与 $Y$ 必须在之前所选择的边被割掉之后任然连通。

$\quad\quad$ (如果想知道割边的具体选择过程,可以参考下文中的 最小割树的构建 内容,此处不详解)

$\quad\quad$ 考虑连通性:我们每次割的过程会把某两个连通的点变得不连通。

$\quad\quad$ 因此,我们每一次“割”的过程,都会把一个原有的连通块分成两个新的连通块,即连通块个数 $+1$,又因为我们最多有 $n$ 个连通块(每个点各算一个),所以我们最多割 $n-1$ 次,故最多有 $n-1$ 个单位元。

$\quad\quad$ 因为某两个点之间的最小割的值本质上就是对某一些“单位元”进行 $\min$ 操作,所以给定一张 $n$ 个点的无向图,最多只有 $n-1$ 种本质不同的最小割。

$\quad\quad$ (总感觉这里没讲清楚,如果没有看懂证明可以先通读全文,尤其是下文关于 最小割树 的干货,然后再回来看定理证明 [虽然我个人觉得不会有人在意这个的证明])

$
$

$\quad$ $2-2:$引理证明(建议跳过):

$\quad\quad$ 注:以下大小写字母等价,小写字母表示原图操作后的情况。

  • $\quad\quad$ 引理一:任取连通两点 $A,B$,割去 $\operatorname{Cut}(A,B)$ 之后,图分为两个连通块,取 $C$ 为 $A$ 所在连通块中的任一点, $D$ 为 $B$ 所在连通块中的任一点,有 $\operatorname{Cut}(A,B) \ge \operatorname{Cut}(C,D)$

$\quad\quad$ 证明一:假设 $\operatorname{Cut}(A,B) < \operatorname{Cut}(C,D)$,那么,割断 $\operatorname{Cut}(A,B)$ 后,$\operatorname{Cut}(C,D)$ 并没有被割断,$C$ 与 $D$ 连通,而 $A$ 与 $C$ 在同一连通块内,故 $A$ 与 $C$ 连通,同理,$B$ 与 $D$ 连通,所以 $A,B$ 任然连通,与 $A,B$ 被割断这一事实矛盾,引理得证(这个引理很好感性理解来着)。

$
$

  • $\quad\quad$ 引理二:任取不同的三点 $A,B,C$,有 $\operatorname{Cut}(A,C) \ge \min(\operatorname{Cut}(A,B),\operatorname{Cut}(B,C))$。

$\quad\quad$ 证明二:割去 $\operatorname{Cut}(A,C) $,不妨假设割断后$B , C$ 两点任然连通(若 $B,C$ 不连通,那么 $A,B$ 一定连通,故同理即可)。由引理一得:$\operatorname{Cut}(A,C) \ge \operatorname{Cut}(A,B)$,故$\operatorname{Cut}(A,C) \ge \min(\operatorname{Cut}(A,B),\operatorname{Cut}(B,C))$(大于 $\min$ 中的任意一个值,就必定恒大于 $\min$),引理得证(这玩意可以类比三角形两边之和大于第三边,不过这里不是和,而是最小值)。

$
$

  • $\quad\quad$ 引理三:任取连通两点 $A,B$,割去 $\operatorname{Cut}(A,B)$ 之后,图分为两个连通块,若 $C$ 与 $A$ 连通,则有 $\operatorname{Cut}(B,C) = \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C))$。

$\quad\quad$ 证明三:根据引理一,有: $\operatorname{Cut}(A,B) \ge \operatorname{Cut}(B,C)$,根据引理二,又有 $\operatorname{Cut}(B,C) \ge \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C))$。

$\quad\quad$ 下面分情况讨论:

$\quad\quad$ 假如 $\operatorname{Cut}(A,B)\le\operatorname{Cut}(A,C)$,那么$\operatorname{Cut}(B,C) \ge \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C))=\operatorname{Cut}(A,B)$,又$\operatorname{Cut}(A,B) \ge \operatorname{Cut}(B,C)$,故$ \operatorname{Cut}(B,C)=\operatorname{Cut}(A,B)=\min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C))$,所证等式成立。

$\quad\quad$ 假如 $\operatorname{Cut}(A,B)>\operatorname{Cut}(A,C)$,那么考虑在原图中割断 $\operatorname{Cut}(A,C)$。

$\quad\quad$ $\quad\quad$ 假若割断后 $A,B$ 不连通,那么 $\operatorname{Cut}(A,B)$ 显然不是割断 $A,B$ 的最优解,与条件矛盾。

$\quad\quad$ $\quad\quad$ 假若割断后 $A,B$ 连通,那么根据引理一,有 $\operatorname{Cut}(A,C)\ge\operatorname{Cut}(B,C)$,又因为$\operatorname{Cut}(B,C) \ge \min(\operatorname{Cut}(A,B),\operatorname{Cut}(A,C)) = \operatorname{Cut}(A,C)$,故假设与条件矛盾。

$\quad\quad$ 因此,当 $\operatorname{Cut}(A,B)\le\operatorname{Cut}(A,C)$ 时,等式成立,而 $\operatorname{Cut}(A,B)>\operatorname{Cut}(A,C)$ 的情况不可能出现。引理得证(这个引理其实可以看做引理二在割边后的特殊形式,在式子上不过是把引理二的大于等于换成了等于)。

$
$


$
$

$\quad$ $3-1:$最小割树定义:

$\quad\quad$ 最小割树(Gomory-Hu Tree)主要用来解决点对之间最小割问题。

$\quad\quad$ 它利用 给定一张 $n$ 个点的无向图,任意两点间的最小割数值最多只有 $n-1$ 种 这一定理,把图上跑的最小割问题,转化为了树上某一路径上边权的最小值的问题,以降低多次询问某两点间最小割的复杂度。

$\quad\quad$ 其定义是:定义一棵树 $T$ 为最小割树,当且仅当对于树上的所有边$(s,t)$,树上去掉$(s,t)$后产生的两个连通块中的点的集合,恰好是原图上$(s,t)$的最小割把原图分成的两个连通块中的点的集合,且边$(u,v)$的权值等于原图上$(u,v)$的最小割。

$
$

$\quad$ $3-2:$最小割树构建:

$\quad\quad$ 1.于当前连通块中任取两个点 $x,y$ ,求出两点在原图中的最小割 $cut$(注意是原图)。

$\quad\quad$ 2.于最小割树中建立连接 $x,y$ 的边,边权为 $cut$。

$\quad\quad$ 3.在当前连通块内也割去 $cut$,于割去 $cut$ 后分裂成的两个新连通块内分别重复 1,2 ,3 过程,直到当前连通块仅剩一个点。

$\quad\quad$ 示例(大写字母组成的是图,小写字母组成的是最小割树,加粗的大写字母是接下来要割的节点,每个块内接下来要割的节点可任意选定):

$\quad\quad$ 选中点 $A,B$。

$\quad\quad$ 割开 $A,B$。于最小割树中建边,在两个新的连通块内分别选中 $B,C$ 节点和 $A,E$ 节点。

$\quad\quad$ 割开,建边,再选中。

$\quad\quad$ 重复过程,直到最后(这里直接跳到最后),得到最小割树。

$\quad\quad$ 看上去,最小割树的构造过程很麻烦,其实在代码层面上并非如此。

$\quad\quad$ 我们可以利用分治思想,简单地构造最小割树,代码放于算法讲解之后,如有兴趣可以提前查看。

$
$

$\quad$ $3-3:$最小割树性质:

$\quad\quad$ 最小割树有一个神奇的性质:原图中任意两点间的最小割等价于最小割树上这两点路径上的边权的最小值。

$\quad\quad$ 构造演示的图中并未标出边权权值,这里给出一张样例图和其最小割树,建议读者自己也动手试一试。

$\quad\quad$ 利用这一性质,所有对原图中两点间最小割的询问都可以被转化为树上最小值的问题,倍增算法即可解决。

$\quad\quad$ 假设原图有 $n$ 个点,$m$ 条边,询问 $Q$ 次最小割,那么朴素做法复杂度是 $O(n^2mQ)$,储存已经计算过的值可以使复杂度降至 $O(n^2m\min(Q,n^2))$,可看做 $O(n^4m)$。

$\quad\quad$ 而最小割树复杂度是 $O(n^2mn+Qlogn)$,可以看做 $O(n^3m)$。

$\quad\quad$ 关于最小割树性质的证明,其实已经在之前的证明(尤其是引理三)中出现了大半了,这里就不赘述了。

$
$


$
$

$\quad$ $4:$代码与练习(代码以洛谷P4897 【模板】最小割树为例):

$\quad\quad$ 最小割树最麻烦的地方在于构建,这里分析构建的实现:

$\quad\quad$ 我们知道,最小割树构建的时候是要处理连通块的分裂(割去某些边,变成两个连通块,然后分别递归处理)的,难道我们真的作一个图然后一次次的分裂吗?

$\quad\quad$ 不,我们可以直接用线段模拟这一过程。

$\quad\quad$ 最开始时,所有点都在同一个连通块内,表现在线段上,就是所有点都在连续的一条线段上。

$\quad\quad$ 割断某一组割边后,原本的一个连通块会变成两个。我们把其中某一组连通块的点全部染成红色,另一组染成绿色。

$\quad\quad$ 我们不妨把所有涂成红色的点移到左边,把所有涂成绿色的点移到右边,变成这样:

$\quad\quad$ 这样一来,左边的所有点属于某一个连通块,右边的点属于另一个连通块,根据最小割树的构造原则,我们可以直接将左右两段递归处理,而不需要真的构图和分裂。

$\quad\quad$ 代码如下:

    void build(int l, int r)
    {
        if(l == r) return ;

        Dinic::S = pla[l], Dinic::E = pla[r];
        int flow = Dinic::Dinic();
        link[pla[l]].push_back(node(pla[r], flow));
        link[pla[r]].push_back(node(pla[l], flow));

        int L = l, R = r;
        for(int k = l; k <= r; k++)
            if(Dinic::deep[pla[k]] != 0x3f3f3f3f)
                tem[L++] = pla[k];
            else
                tem[R--] = pla[k];
        for(int k = l; k <= r; k++)
            pla[k] = tem[k];

        build(l, L - 1), build(L, r);
    }

$\quad\quad$ 首先是变量的定义,$S,E,deep$是 Dinic 算法中的量,含义显然,$link$ 是最小割树上的边。

$\quad\quad$ 函数的两个参数 $l,r$ 代表当前处理的连通块在线段上的左右端点,$pla$ 代表在线段当前位置的节点的编号是多少(我们在线段上移动了节点,所以线段的 $i $ 位置并不一定是 $i$ 号点),$tem$ 是移动线段时的辅助数组。

$\quad\quad$ 分析代码:首先 if(l == r) return ; 代表递归的边界,即在线段左右端点重合(连通块内仅一个点)的时候跳出。

$\quad\quad$ Dinic::S = pla[l], Dinic::E = pla[r]; 代表从区间中选取两个点的过程,本质上任取两个不重复的点就可以了,这里取左右端点仅仅是为了方便。

$\quad\quad$ 下面这三句是算出最小割并往最小割树里加边的过程,不要忘了在每一次跑最大流之前还原每条边的流量。

    int flow = Dinic::Dinic();
    link[pla[l]].push_back(node(pla[r], flow));
    link[pla[r]].push_back(node(pla[l], flow));

$\quad\quad$ 下面这一段是找出红绿两色点的过程,建立左右指针,红点插左指针,绿点插右指针,为了防止原数组被破坏,我们需要把它们插到一个辅助数组里,并在最后把辅助数组赋值给位置数组。

$\quad\quad$ 如何找出红绿两色点?在 Dinic 过程中,最后一次 bfs 触碰到的点的 $deep $ 不是初始值,而触碰到的点恰好是 $S$ 所在连通块内的点,可以看做同一种颜色,剩下的点自然是另一种颜色了。

    int L = l, R = r;
    for(int k = l; k <= r; k++)
        if(Dinic::deep[pla[k]] != 0x3f3f3f3f)
            tem[L++] = pla[k];
        else
            tem[R--] = pla[k];
    for(int k = l; k <= r; k++)
        pla[k] = tem[k];

$\quad\quad$ 最后递归下去就好了。

    build(l, L - 1), build(L, r);

$\quad\quad$ 其它部分的代码难度不大,不过要注意细节。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, ch = '~';

    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x;
}

const int N = 900 * 2;
const int M = 40000;

int n, m ;

namespace Dinic
{
    int tot = 1, S, E, max_flow;
    struct node
    {
        int to, flow;
    } edge[M];
    int ori_flow[M];
    vector <int > link[N];

    void add_edge(int u, int v, int w)
    {
        link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = w;
        link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = w;
    }

    int deep[N], cur[N], vis[N];
    queue <int > q;
    bool bfs()
    {
        memset(cur, 0, sizeof(cur));
        memset(vis, 0, sizeof(vis));
        memset(deep, 0x3f, sizeof(deep));
        q.push(S), vis[S] = 1, deep[S] = 0;

        while(!q.empty())
        {
            int pla = q.front();
            q.pop();

            for(int k = 0; k < (int )link[pla].size(); k++)
            {
                int num = link[pla][k], to = edge[num].to;

                if(!vis[to] && edge[num].flow)
                    vis[to] = 1, deep[to] = deep[pla] + 1, q.push(to);
            }
        }

        return deep[E] != 0x3f3f3f3f;
    }

    int dfs(int pla, int flow)
    {
        if(pla == E)
        {
            max_flow += flow;
            return flow;
        }

        int used = 0;
        for(int k = cur[pla]; k < (int )link[pla].size(); k++, cur[pla] = k)
        {
            int num = link[pla][k], to = edge[num].to, Flow;

            if(deep[to] == deep[pla] + 1 && edge[num].flow && (Flow = dfs(to, min(edge[num].flow, flow - used))))
                edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

            if(flow == used) break;
        }

        return used;
    }

    void init()
    {
        for(register int k = 2; k <= tot; k++)
            ori_flow[k] = edge[k].flow;
    }

    int Dinic()
    {
        max_flow = 0;
        for(register int k = 2; k <= tot; k++)
            edge[k].flow = ori_flow[k];

        while(bfs())
            dfs(S, 0x3f3f3f3f);
        return max_flow;
    }
}

namespace GHT//Gomory_Hu_Tree
{
    int pla[N], tem[N], deep[N];
    int f[N][10], g[N][10];

    struct node
    {
        int to, len;

        node (int a, int b)
        {
            to = a, len = b;
        }
        node () { }
    };
    vector <node > link[N];

    void build(int l, int r)
    {
        if(l == r) return ;

        Dinic::S = pla[l], Dinic::E = pla[r];
        int flow = Dinic::Dinic();
        link[pla[l]].push_back(node(pla[r], flow));
        link[pla[r]].push_back(node(pla[l], flow));

        int L = l, R = r;
        for(int k = l; k <= r; k++)
            if(Dinic::deep[pla[k]] != 0x3f3f3f3f)
                tem[L++] = pla[k];
            else
                tem[R--] = pla[k];
        for(int k = l; k <= r; k++)
            pla[k] = tem[k];

        build(l, L - 1), build(L, r);
    }

    void dfs(int pla, int fa)
    {
        deep[pla] = deep[fa] + 1;
        for(int k = 1; k < 10; k++) f[pla][k] = f[f[pla][k - 1]][k - 1];
        for(int k = 1; k < 10; k++) g[pla][k] = min(g[pla][k - 1], g[f[pla][k - 1]][k - 1]);

        for(int k = 0; k < (int )link[pla].size(); k++)
        {
            int to = link[pla][k].to;
            int len = link[pla][k].len;

            if(to != fa)
                g[to][0] = len, f[to][0] = pla, dfs(to, pla);
        }
    }

    int min(int u, int v)
    {
        int ans = 0x3f3f3f3f;
        if(deep[u] < deep[v]) swap(u, v);

        for(int k = 9; k >= 0; k--)
            if(deep[u] - (1 << k) >= deep[v])
                ans = std::min(ans, g[u][k]), u = f[u][k];

        if(u == v) return ans;

        for(int k = 9; k >= 0; k--)
            if(f[u][k] != f[v][k])
                ans = std::min(ans, g[u][k]), ans = std::min(ans, g[v][k]), u = f[u][k], v = f[v][k];

        return std::min(std::min(ans, g[u][0]), g[v][0]);
    }
}

int main()
{
    memset(GHT::g, 0x3f, sizeof(GHT::g));
    n = read() + 1, m = read();
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read(), w = read();
        Dinic::add_edge(u + 1, v + 1, w);
    }
    Dinic::init();

    for(register int k = 1; k <= n; k++)
        GHT::pla[k] = k;
    GHT::build(1, n);
    GHT::dfs(1, 0);

    int Q = read();
    for(register int k = 1; k <= Q; k++)
    {
        int u = read(), v = read();
        printf("%d\n", GHT::min(u + 1, v + 1));
    }

    return 0;
}

$
$

$\quad\quad$ 例题:洛谷P4123 [CQOI2016]不同的最小割

$\quad\quad$ 没啥好说的,因为只需要处理有多少种权值,甚至连最小割树都不需要建出来。

$\quad\quad$ 代码:

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, ch = '~';

    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x;
}

const int N = 900 * 2;
const int M = 40000;

int n, m ;

namespace Dinic
{
    int tot = 1, S, E, max_flow;
    struct node
    {
        int to, flow;
    } edge[M];
    int ori_flow[M];
    vector <int > link[N];

    void add_edge(int u, int v, int w)
    {
        link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = w;
        link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = w;
    }

    int deep[N], cur[N], vis[N];
    queue <int > q;
    bool bfs()
    {
        memset(cur, 0, sizeof(cur));
        memset(vis, 0, sizeof(vis));
        memset(deep, 0x3f, sizeof(deep));
        q.push(S), vis[S] = 1, deep[S] = 0;

        while(!q.empty())
        {
            int pla = q.front();
            q.pop();

            for(int k = 0; k < (int )link[pla].size(); k++)
            {
                int num = link[pla][k], to = edge[num].to;

                if(!vis[to] && edge[num].flow)
                    vis[to] = 1, deep[to] = deep[pla] + 1, q.push(to);
            }
        }

        return deep[E] != 0x3f3f3f3f;
    }

    int dfs(int pla, int flow)
    {
        if(pla == E)
        {
            max_flow += flow;
            return flow;
        }

        int used = 0;
        for(int k = cur[pla]; k < (int )link[pla].size(); k++, cur[pla] = k)
        {
            int num = link[pla][k], to = edge[num].to, Flow;

            if(deep[to] == deep[pla] + 1 && edge[num].flow && (Flow = dfs(to, min(edge[num].flow, flow - used))))
                edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

            if(flow == used) break;
        }

        return used;
    }

    void init()
    {
        for(register int k = 2; k <= tot; k++)
            ori_flow[k] = edge[k].flow;
    }

    int Dinic()
    {
        max_flow = 0;
        for(register int k = 2; k <= tot; k++)
            edge[k].flow = ori_flow[k];

        while(bfs())
            dfs(S, 0x3f3f3f3f);
        return max_flow;
    }
}

set <int > s;

namespace GHT//Gomory_Hu_Tree
{
    int pla[N], tem[N];

    void build(int l, int r)
    {
        if(l == r) return ;

        Dinic::S = pla[l], Dinic::E = pla[r];
        int flow = Dinic::Dinic();
        s.insert(flow);
        int L = l, R = r;

        for(int k = l; k <= r; k++)
            if(Dinic::deep[pla[k]] != 0x3f3f3f3f)
                tem[L++] = pla[k];
            else
                tem[R--] = pla[k];
        for(int k = l; k <= r; k++)
            pla[k] = tem[k];

        build(l, L - 1), build(L, r);
    }
}

int main()
{
    n = read(), m = read();
    for(register int k = 1; k <= m; k++)
    {
        int u = read(), v = read(), w = read();
        Dinic::add_edge(u, v, w);
    }
    Dinic::init();

    for(register int k = 1; k <= n; k++)
        GHT::pla[k] = k;
    GHT::build(1, n);

    printf("%d", (int )s.size());

    return 0;
}

$\quad\quad$ 练习:UVA11594 All Pairs Maximum Flow,代码就不放了,基本上还是模板。

$
$


结语:

$\quad\quad$ 最小割树的用处其实是不大的,但其算法的思想值得学习。

$\quad\quad$ 而且它是一个并不难,但是评级高的算法,黑模板题它的不香吗?

$\quad\quad$ 另外,证明过程并不保证正确(毕竟都是作者口胡出来的),若有误请联系作者Orz。

$
$

$$\large {E \ N \ D}$$




Sata_星空
5个月前

N方 D P 要A掉

斜率优化少不了

[HTML_REMOVED]

前言:

$~\$

$\quad\quad$ 曾经看过斜率优化…当时没有看懂。

$\quad\quad$ 因为 CSP/NOIP 也不用…当时就没怎么在意。

$\quad\quad$ 今天花了半个下午,A掉了斜率优化的板子…写一篇学习笔记加以巩固…

$~\$

$\quad\quad$ Update(20/06/18):修复了一些细节错误。


$~\$

正文:

$\quad\quad$ 下面首先用一道例题引出这个知识点。

  • 题目大意:把 $n$ 个物品分成若干组,某组中不同物品间要空一个单位长度,物品长度为 $C_i$ ,每一组会带来该组长度 $l$ 与某一固定常数 $L$ 之差的平方的代价。求最小代价和。

$\quad\quad$ 本题 DP 方程显然:设 $f(i)$ 为把前 $i$ 个物品放置好的最小代价,则有

$$f(i)=min((S(j+1,i)+i-j-1-L)^2+f(j))$$

$\quad\quad$ 式子的实际意义是枚举上一个容器的终止节点,其中 $S(i,j)$ 代表 $i - j$ 物品的长度和。

$\quad\quad$ 显然,转移内部的$j$需要从 $0$ 穷举到 $k-1$,总复杂度为$O(n^2)$。

  • 裸 $DP$ 代码(变量名有些不一样):
for(int k = 1; k <= n; k++)
    for(int i = 0; i < k; i++)
        f[k] = min(f[k], f[i] + (int )pow((cl[k] - cl[i] + k - i - 1 - L, 2));
//cl为C的前缀和 

$~\$

$\quad\quad$ 观察数据规模:$1<=n<=5*10^4 $, $O(n^2)$ 是显然跑不过去的。

$\quad\quad$ 如何优化本题的时间复杂度?外层的$1$~$n$的循环很难优化,考虑从内层循环下手。

$\quad\quad$ 观察 DP 方程里 ,$min((S(j+1,i)+i-j-1-L)^2+f(j))$ 这一部分似乎和单调队列优化有关。

$\quad\quad$ 单调队列可优化 $f(i)=min(f(j)+X)$ 的过程,但要求 $X$ 是常数,而这里的 $(S(j+1,i)+i-j-1-L)^2$ 显然与 $i$ 有关,所以不能简单当做常数。所以不能使用单调队列优化,但是可以使用斜率优化。

$~\$


$\quad\quad$ 斜率优化,顾名思义,是通过斜率对 DP 进行优化,与单调队列优化类似,它的优化是针对转移方式的。

$\quad\quad$ 斜率优化的关键在 “斜率”,让我们对 DP 做一些变形:

$$f(i)=min((S(j+1,i)+i-j-1-L)^2+f(j))$$

$\quad\quad$ 我们先把平方打开,打开的过程中可以考虑换元。

$\quad\quad$ 令$A(i)=cl(i)+i,B(j)=cl(j)+j+1+L$。($cl$ 代表前缀和数组,这里把 $S$ 拆开了)

$\quad\quad$ 这里换元的目的仅仅只是为了好算,没有特定的要求,把 $B[j]$ 里面的常数丢 $A[i]$ 里面也是可以的,换元后的 $A(i),B(j)$ 与 $cl(i),cl(j)$ 类似,仍是关于 $i,j$ 的函数。

$\quad\quad$ 式子变为:

$$f(i) = min(f(j) + (A(i)-B(j))^2)$$

$\quad\quad$ 现在就很好展开了。

$$f(i) = min(f(j) + A(i)^2+B(j)^2-2A(i)B(j))$$

$\quad\quad$ 式子中的函数分为两类,一种是可变的,一种是不可变的。

$\quad\quad$ 首先,所有与 $i$ 有关的数值都可以视作不变,因为我们进行内层循环求 $f(i)$ 时,是对于某一个特定的 $i$ 求的。

$\quad\quad$ 剩下来的与 $i$ 有关的式子都会随 $i$ 改变。

$\quad\quad$ 我们不妨去掉 $min$,这个$min$ 的实际意义是:找到一个 $j$ 使得 $f(i)$ 算出来最小,我们只需要找到这个 $j$ 就可以了。

$$f(i) = f(j) + A(i)^2+B(j)^2-2A(i)B(j)$$

$\quad\quad$ 我们稍微移一下项$-----$①

$$B(j)^2+f(j)=2A(i)B(j)+f(i)-A(i)^2$$

$\quad\quad$ 移项后,等式左边的项都只与 $j$ 有关,等式右边的 $B[j]$ 也与 $i$ 有关,其余的项都是常数。

$\quad\quad$ 我们不妨把 $B(j)$ 看做自变量 $X$ ,把 $B(j)^2+f(j)$ 看做自变量 $Y$ ,认为是 $B(j)$ 的改变造成了 $B(j)^2+f(j)$的改变,现在式子变成这样:

$$Y=2A(i)X+f(i)-A(i)^2$$

$\quad\quad$ 观察这个方程,剩下项的都是常数,所以它可以看做一个一次函数,令 $2*A(i)$为斜率 $K$ ,$f(i)-A(i)^2$ 为 $y$ 轴上截距 $B$,有:

$$Y=KX+B$$

$\quad\quad$ (从①开始的移项是有通式的:把既与 $i$ 有关,又与 $j$ 有关的项合并在一起,看做$KX$,把只与 $j$ 有关的项看做 $Y$ ,其他的项看做 $B$)

$\quad\quad$ 对于这个函数,$j$ 的取值是一定的($1-i-1$),所以 $X,Y$ 的 取值也是一定的,这么一来, 函数中的 $(X,Y)$ 二元组可以看做坐标系上的定点,如下图。

$\quad\quad$ 我们的目的是求出 $f(i)$ 最小值,所以本质上就是求一条斜率恒定($K=2*A(i)$为定值)的直线,过某个点集中的哪个点,可以获得最小截距($B=f(i)-A(i)^2,B$ 越小,$f(i)$越小)。

$\quad\quad$ 我们做出一条斜率恒定的直线:

$\quad\quad$ 它必须过点集中的某一点,所以我们将它上移,直到与某个节点相交,那时,它的截距最小,有 $f(i)=Y-KX+A(i)^2$,如下图:

$\quad\quad$ 然而,给我们图我们自然可以求,但怎么让电脑找直线与点群的第一个交点呢?

$\quad\quad$ 首先,我们发现点群中有些点是没必要存在的。

$\quad\quad$ 比如说 $F,E,B$ 点,无论直线斜率为多少,只要是求最小截距,就一定轮不到它们。

$\quad\quad$ 所以我们大可以把它们删掉。

$\quad\quad$ 观察这几个点的共通之处,如下图:

$\quad\quad$ 可能被一条斜率为某个值的直线穿过的点连成了一个凸包,显然,凸包外的点不可能第一个与任意斜率的直线相交(前提是我们要让截距最小)。

$\quad\quad$ 所以,我们不需要维护点集,维护一个下凸包就好。

$\quad\quad$ 而本题中的$X($即$B(j))$显然是递增的,所以可以用单调队列维护凸包,如下图:

$\quad\quad$ 原本 $A,B,C,D$ 构成了凸包,插入了节点 $E$ 以后,凸包被打破…

$\quad\quad$ 组成凸包的线段的斜率需要从左往右递增,所以我们可以从被打破的点($D$)开始,向左右删不合条件的节点,直到凸包重新出现。(这个删法对于不同的凸包在不同的方向上是不同的,不给通式,建议自己试一试)

$\quad\quad$ 本图中,$C,E$连成的边,与 $A,B$ 构成了新的凸包。

$\quad\quad$ 本题比较特殊,按照我们的思路,跑完出 $f(i)$ 后,我们求 $f(i+1)$ 的过程中可以直接利用 $f(i)$ 的凸包,只需要在上面再加一个点($B(i),B(i)^2+f(i)$)就行了。

$\quad\quad$ 而 $B(i)$ 又是单调的,所以我们只会在凸包的一侧插入节点,删除不合条件的节点也只需要往一侧删就好了。

$\quad\quad$ 但是还有一个问题:对一个凸包而言,什么时候第一次与一条直线相交?

$\quad\quad$ 显然是凸包与直线 $l$ 相切与某个点的时候。

$\quad\quad$ 根据凸包的性质(这里以图中的凸包为例,不同凸包不一定一样),相切的点左边的,构成凸包的所有线段斜率一定小于 $l$ ,右边的直线则一定大于 $l$。

$\quad\quad$ 本题中又很特殊:当我们按从 $1$ 到 $n$ 的顺序求解 $f(i)$ 时,直线的斜率 $K$ 递增。

$\quad\quad$ 所以,我们可以判断凸包最左侧的两点连线 $c$ 斜率是否大于直线 $l$,如果大于,那么切点一定是凸包左端点,否则左端点可以删去(类似单调队列,以后的 $l’$ 斜率一定大于$l$,斜率就一定不会小于 $c$)。


$\quad\quad$ 上面讲的很乱,不过大致把本题斜率优化的操作流程讲了一遍,下面总结具体步骤:

1.求出前缀和等必要的量,换元,把 DP 方程写的尽量简单。

2.确定可以使用斜率优化,画图找该维护的凸包,依次算出要求的DP值,这里又分几个小步骤(这几个小步骤在不同的题中不相同,具体要看方程和凸包,下面只是针对这一道题的步骤)

    首先,把单调队列左边的,以后永远用不上的点删掉。

    然后,取队首节点为直线与凸包切点,算出直线方程,求得f(i)。

    接着,在加入f(i)对应的节点(x,y)前,删掉单调队列右边的,在加入(x,y)后会破坏凸包的点。

    最后,加入点(x,y)。

3.输出f(n)

$~\‘$

$\quad\quad$ 步骤的理由和具体操作,上面基本都有,一些细节可以去代码里找。

$\quad\quad$ 注意:初始时,要把$f(0)=0$(这个初始值对不同的题是不一定相同的) 对应的节点放到凸包里面去。

$\quad\quad$ 感觉自己写的不是很清晰,但斜率优化很难弄出一个定式来,它与方程的变量,各变量的单调性息息相关,上面的很多内容都是建立在本题 $XXX$ 有单调性的基础上的,如果没有单调性就会麻烦很多。

  • 代码:
#include <bits/stdc++.h>
#define int long long
//不开long long 见祖宗

using namespace std;

const int N = 50010;

int n, L , C[N] , cl[N] , f[N];

int head = 1, tail = 1, x[N], y[N];

int A(int k)
{
    return cl[k] + k;
}
int B(int k)
{
    return cl[k] + k + 1 + L;
}

//算斜率,不开double都没脸见祖宗
double slope(int a, int b)
{
    return (y[a] - y[b]) / (1.0 * x[a] - x[b]);
}
double slope(int x1, int y1, int x2, int y2)
{
    return (y1 - y2) / (1.0 * x1 - x2);
}

signed main()
{
    scanf("%lld %lld", &n, &L);
    for(int k = 1; k <= n; k++)
        scanf("%lld", &C[k]), cl[k] = cl[k - 1] + C[k];

    x[tail] = B(0), y[tail++] = B(0) * B(0);

    for(int k = 1; k <= n; k++)
    {
        //进格
        while(head + 1 < tail && slope(head, head + 1) < 2 * A(k))
            head++;

        //计算
        f[k] = y[head] - 2 * A(k) * x[head] + A(k) * A(k);
        int new_x = B(k), new_y = f[k] + B(k) * B(k);

        //退格
        while(head + 1 < tail && slope(x[tail - 1], y[tail - 1], new_x, new_y) < slope(tail - 1, tail - 2))
            tail--;

        //填入
        x[tail] = new_x, y[tail++] = new_y;
    }

    printf("%lld", f[n]);

    return 0;
}

结语:

$\quad\quad$ 首先是关于方程对应转化的问题,这里总结一下。

$\quad\quad$ 对于 $Y=KX+B$,如果求 $B_{min}$,就维护下凸包,否则维护上凸包。

$\quad\quad$ 如果 $X$ 递增,那么插入值时在右侧插入,递减则在左侧插入,没有单调性需要在中间插入,往两边拓展。

$\quad\quad$ 如果 $K$ 递增,那么可以仅维护凸包右侧的部分,如果递减可以仅维护凸包左侧的部分,如果无单调性需要二分找切点。

$\quad\quad$ 最后放一波刷题列表:

$\quad\quad$ 洛谷 P5785 [SDOI2012]任务安排(斜率非单调)

$\quad\quad$ 洛谷 P3628 [APIO2010]特别行动队(板子)

$\quad\quad$ 洛谷 P2120 [ZJOI2007]仓库建设(看两眼就出来了)

$\quad\quad$ 洛谷 P3648 [APIO2014]序列分割 (有点毒瘤…)

$~\$

$$\huge\color {#123456} \mathcal {E \ N \ D}$$