基础图论知识拓展

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

基础图论知识拓展

作者：

Sata_星空 , 2020-06-17 15:10:16 , 所有人可见 , 阅读 974

5

7

前言：

$~\\$

$\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$求最短路的证明相同，这里略去。

$~\\$

例题：UVA247 电话圈 Calling Circles

解析：板子，解析略。
代码：

#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’$ 的时候取得。

$~\\$

例题：洛谷 P6175 无向图的最小环问题

代码：

#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$也是没有问题的。事实上，第一层循环枚举节点的顺序是任意可变的。一些题目可以利用这个性质解决。

$~\\$

例题：洛谷 P1119 灾后重建

解析：如果不管题面的“未修复完成”这一条件，那么本题便是一道最短路的模板题。我们观察题目条件：村庄是依次修复完毕的，我们不能经过未修复的村庄。或者换一种说法，我们只能通过已修复的村庄中转。“经过某些点中转”正对应着我们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。

例题：bzoj3040 最短路(road)

解析：最短路板子题，但是可以卡掉没有优化的$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<y$（如果$x>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)$查询，从而解决多次询问最小瓶颈路的问题。

$~\\$

例题：UVA10048 【噪音恐惧症】

代码：

#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$ 仍然以上面那题作为例题，这里就不多放图了，解析和代码可以看我写的一篇题解：

$~\\$

练习：洛谷P4768 [NOI2018]归程

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

$~\\$

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

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

$~\\$

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

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

例题：UVA11324 The Largest Clique

解析：这样的题目的一般思路是：先思考怎么把一个强连通缩成一个点，再思考图变为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;
}

练习：洛谷P2403 [SDOI2010]所驼门王的宝藏

$\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)$，那么该边就在最短路网上。

例题：洛谷P2149 [SDOI2009]Elaxia的路线

解析：观察题目，我们注意到：两人比起“在一起的时间最长”，更期望“走的路程最短”。换句话说，最短路是第一关键字，是在走最短路的前提下重叠最长。所以我们可以先跑出最短路网，在最短路网之外的其它边是完全没有意义的（因为两人走最短路不会经过那些边）。然后，我们所求的就是最短路网交集中的最长链，把最短路网中的分别标记一下，如果一条边同时被两个最短路网所标记，那么它就在最短路网的交集中，我们把交集中的点拿出来再建图，很显然，建出来的图也是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;
}

练习：洛谷P2505 [HAOI2012]道路

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

$~\\$

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

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

$~\\$

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

例题：P4802 [CCO 2015]路短最

解析：本题状压的思路非常明显：$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;
}

$~\\$

例题：牛客CSP-S提高组赛前集训营5B 十二桥问题

解析：本题比上一题复杂一些，从必须经过节点变成了必须经过边。我们发现，本题要经过的边数仅仅只有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权。

$~\\$

例题：UVA10269 Adventure of Super Mario

解析\代码：推销自己的题解

$~\\$

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

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

例题：UVA10603 倒水问题 Fill

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

$~\\$

例题：UVA658 这不是bug，而是特性 It’s not a Bug, it’s a Feature!

解析：本题稍微有些麻烦。拿到本题时，第一反应大概是搜索，看看数据规模，似乎可以记忆化。然而，我们发现，从某些状态搜索下去有可能重新达到这个状态。这导致我们的记搜会陷入无限递归。因此，我们无法用记搜做这道题。（根本原因是这图不是个 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…

0 评论

App 内打开