最短路

最短路是非常常见的问题，求解方法和各种应用也很多，首先来看一些常用的、基本的最短路求法。

Floyd

Floyd是一种用DP求解最短路的方法，基本思想就是；对于每个起点和终点，枚举中间点，进行状态转移。
转移方程为$d_{x,y}=\min\{d_{x,k}+d_{k,y}|1\le k\le n\}$
其时间复杂度为$O(n^3)$，主要用来求任意两点间的最短路。
除了Floyd算法，下面的其他最短路算法都是单源最短路的求解。

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (d[i][j] > d[i][k] + d[k][j])
                d[i][j] = d[i][k] = d[k][j];

Bellman-Ford（SPFA）

Bellman-Ford算法最核心的操作称为松弛操作，其思想为：用当前节点的最短路更新其连接点的最短路。
朴素的Bellman-Ford算法非常暴力，直接遍历所有点进行松弛操作，直到没有点可以被松弛，这样做复杂度显然是非常高的，于是我们考虑用队列来进行优化，将所有更新过的点加入队列，每次取出一个点进行松弛，直到队列为空，这便是SPFA。

但是即使用队列优化过，SPFA依然复杂度很高，为$O(|V|\cdot|E|)$，只是大多数情况下可以跑得很快，利用网格图之类的特殊结构可以卡掉这种算法，所以如果题目中明显是没有负边的，求最短路的时候我们采用别的方法。

void spfa(int st) {
    dist[st] = 0;
    queue<int>q;
    q.push(st);
    while (!q.empty()) {
        int k = q.front(); q.pop();
        flag[k] = false;
        for (int e = p[k]; e; e = nt[e]) {
            int kk = b[e];
            //下面是松弛操作，由于dist初始化值较大，我们将不等式变形
            if (dist[kk] - dist[k] > w[e]) {
                dist[kk] = dist[k] + w[e];
                if (!flag[kk]) {
                    q.push(kk);//kk不在队列中则入队
                    flag[kk] = true;
                }
            }
        }
    }
}

负环判定

SPFA有一个好处（~~大概是唯一一个~~）就是不怕负边以及可以判定负环，判定方法也很简单，我们可以记录每个点入队的次数，如果这个次数达到了总节点数说明图中存在负环。

差分约束系统

差分约束系统用于将不等式问题转换成最短路问题并求解，我们对于不等式$a-b\ge c$连边a to b，边权为-c，表示的是从a到b至少需要减少c，那么求完最短路后，a与b的差就是大于等于c的。
以下不等式都可以变成上述形式建边：
$a - b > c即a-b\ge c+1$
$a-b\le c即b-a\ge -c$
$a-b < c即b-a\ge -c+1$
$a-b=c即a-b\ge c且b-a\ge -c$
$a-b\not= c即b-a\ge-c + 1或a-b\ge c + 1$

然后我们跑一遍SPFA，如果出现负环说明无解，否则我们可以跑出一组解。

上模板洛谷P5960 【模板】差分约束算法

int dist[N], num, p[N], b[N], nt[N], w[N], de[N], in[N], n, m;
bool flag[N];
void add(int x, int y, int z) {
	b[++num] = y, w[num] = z;
	nt[num] = p[x], p[x] = num;
}
void spfa(int st) {
	dist[st] = 0;
	queue<int>q;
	q.push(st);
	while (!q.empty()) {
		int k = q.front(); q.pop();
		flag[k] = false;
		for (int e = p[k]; e; e = nt[e]) {
			int kk = b[e];
			if (dist[kk] - dist[k] > w[e]) {
				dist[kk] = dist[k] + w[e];
				if (!flag[kk]) {
					q.push(kk);
					flag[kk] = true;
					if (++in[kk] > n) {
						puts("NO");//出现负环
						exit(0);
					}
				}
			}
		}
	}
}

int main() {
	n = fast_IO::read(), m = fast_IO::read();
	for (int i = 1; i <= m; ++i) {
		int a = fast_IO::read(), b = fast_IO::read(), c = fast_IO::read();
		add(b, a, c);
        //a - b <= c
        //化为b - a >= -c
        //根据前面的结论，连边b->a，边权为c
	}
	memset(dist, 63, sizeof(dist));
	for (int i = 1; i <= n; ++i)add(n + 1, i, 0);//超级源连上所有点
	spfa(n + 1);//跑最短路
	for (int i = 1; i <= n; ++i)
		fast_IO::write(dist[i]), putchar(' ');
	return 0;
}

Dijkstra

Floyd是如此之慢！SPFA也是如此之慢！那么我们怎么求点数和边数在1e5级别的单源最短路呢？
我们使用Dijkstra算法来解决这样的问题，Dijkstra本质是贪心和BFS求最短路，其基本思想是保证每个点只能遍历一次，每次去找dist最小的点对其连接的点进行更新。
更具体地，将Dijkstra算法过程描述为：从源点的dist=0开始，每次取出优先队列中最小的点并打上标记，对其连接的点进行更新，然后将其连接的没有打标记的节点加入优先队列，重复操作直到优先队列为空。
如何说明其正确性呢？直观来看确实很难说明，但我们可以用反证法来简单证明。
假设点x在出队后优先队列中还有点y可以使dist[x]减小，那么dist[y]必然小于dist[x]，而根据优先队列的性质，dist[x]大于等于x出队后优先队列内任何一点的dist值，即$dist[x]\ge dist[y]$，矛盾。因此可以保证x出队后其dist值是最小的。

struct Node {
	int bh;
	ll dist;
	Node(){}
	Node(int bh, ll dist): bh(bh), dist(dist) {}
	bool operator <(const Node s)const { return dist > s.dist; }
};
priority_queue<Node>q;
void dijkstra(int st) {
    //dist初始化为较大值
	dist[st] = 0;
	q.push(Node(st, 0));
	while (!q.empty()) {
		Node k = q.top(); q.pop();
		if (flag[k.bh])continue;
		flag[k.bh] = true;
		for (int e = p[k.bh]; e; e = nt[e]) {
			int kk = b[e];
			if (dist[kk] - dist[k.bh] > w[e]) {
				dist[kk] = dist[k.bh] + w[e];
				if (!flag[kk])q.push(Node(kk, dist[kk]));
			}
		}
	}
}

Tarjan

tarjan是非常实用的图论算法，使用tarjan可以解决很多图论问题。

强连通分量

首先我们来看tarjan的一个经典应用：求有向图强连通分量（联通块）。
强连通分量，即图的一个子集，其中每个点都可以到达其他任意一个点。
要想搞清楚tarjan算法，主要是要弄明白这两个数组有何作用、如何实现：dfn和low
其中dfn[x]较为简单，其含义为x的搜索序，你也可以理解为dfs过程中x的时间戳。
重点需要理解的是low[x]的含义，一般来说我们描述为“他表示从x处开始搜索，能走到的最小的搜索序是多少。”
但实际上这个说法是比较含糊的，与x连接的某个点为k，则从x处开始搜索时不能搜回fa处，且若k在此前其在x后已经搜索过，则不再继续搜索，并用dfn[k]更新low[x]的值，而对于其他连接的节点，需要取其low最小值。
对于k，我们用其dfn值更新x的low值的原因是，从x处能搜到曾经搜过的k，那么从k开始就有可能存在一个强联通块包含了x，因此我们将x的low值更新，再通过回溯时对low值的更新，一步步更新回k点，若low[k]与dfn[k]相等，就说明从k开始绕了一圈又找到了k，也就是说找到了强连通分量。
那么如何对应地找到其中所有的节点呢？我们通过栈来实现，在dfs过程中，若遇到没搜过的点，则将其入栈，最后在low[x]=dfn[x]处，因为从x处最终能走回x，回溯到x时，途中的所有节点都在栈中，而中途可能遇到的分支都会在相同的过程中全部出栈（不在环中的自成一个强连通分量），因此从栈顶到栈中x的位置，中间的节点正好在一个强连通分量中，所以我们只需要不断弹栈，直到将x弹出栈，所有弹出的元素都归为一个强联通块中，可以证明，这样求得的强联通块是最大强联通块，将强联通块抽象成点，这便是缩点。

void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    st[++top] = x;
    flag[x] = true;//在栈中
    for (int e = p[x]; e; e = nt[e]) {
        int k = b[e];
        if (!dfn[k]) {
            tarjan(k);
            low[x] = min{low[x], low[k]);}
        }
        else if (flag[k])low[x] = min(low[x], dfn[k]);
        //从某点出发的路径中有k（因为k还在栈中），则可能会成环。
    }
    if (dfn[x] == low[x]) {
        //相等则成环
        ++totltk;//联通块数量+1，也表示了当前联通块数量
        while (st[top + 1] != x) {
            ltk[st[top]] = totltk;
            f(totltk, x);//可能通过x对联通块内进行一些信息的统计
            flag[st[top]] = false;//标记出栈
            --top;
        }
        //将栈中元素弹出至x也被弹出
    }
}

割点（割顶）

理解了如何计算并使用dfn及low后，我们来看如何求无向图的割点。
割点指的是若将联通无向图中的某点及其连接的边删去后，图中连通分量个数增加，则称这个点为割点。
其中求dfn与low的过程与求强连通分量的过程基本相同，但我们不需要使用栈，对于任何一个走过的点我们都用其dfn值更新x的low值，至于具体原因，首先我们需要知道怎么求出割点。
对于x，假设其从fa搜索过来，连接着某点k，则若low[k]==dfn[x]，说明x为割点。
为什么呢？因为如果将x删掉，k与fa必然不属于同一个联通块，若删掉x后k与fa属于同一个联通块，那么low[k]必然会小于dfn[x]，这也就是为什么我们对每个走过的点都用其dfn值更新x的low值，就是为了保证求出的割点一定能保证k与fa不在任何同一个联通块中。
然后我们就会考虑到一个特殊的点：第一个搜索的点，这个点是没有fa的。那么如何确定第一个点是不是割点呢？我们记录第一个点被包含在多少个最大的除去x后的联通块中，其实也就是在第一个点进行连接点的遍历时，若该点没有访问过则算入记录，这个应该比较显然，那么只要这个记录比1大，就说明将x删去后会产生多个联通块，即x为割点。
于是我们的算法就出来了

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++tot;
    int child = 0 ;
    for (int e = p[x]; e; e = nt[e]) {
        int k = b[e];
        if (!dfn[k]) {
            tarjan(k, x);
            if (low[k] == dfn[x] && x != fa)gd[x] = true;//是割点
            low[x] = min(low[x], low[k]);
            if (x == fa)child++;//统计我们要的东西
        }
        else low[x] = min(low[x], dfn[k]);//全部更新
    }
    if (child >= 2)flag[x] = true;//是割点
}

另外，根据上述求法，我们还可以统计出断开点x后联通块增加的个数：
对于第一个搜索的点，显然联通块增加的个数就是child - 1；
对于其他的点，联通块增加的个数应当是x被判为割点的次数。

if (low[k] == dfn[x] && x != fa)gd[x] = true;
改为
if (low[k] == dfn[x] && x != fa)++delta[x];

if (child >= 2)flag[x] = true;
改为
if (child >= 2)delta[x] = child - 1;

桥

在无向图中，若删去某边使得图的联通块数量增加，则该边称为桥。
桥的求法非常简单，根据其定义，只要删去该边联通块数量增加的就是桥，因此在tarjan的过程中，若我们通过某条边找到的low值比dfn[x]大，说明该边就是桥。

void tarjan(int x) {
    dfn[x] = low[x] = ++*dfn;
    st[++*st] = x;
    flag[x] = true;
    for (int e = p2[x]; e; e = nt2[e]) {
        int k = b2[e];
        if (vis[e])continue;
        if (!dfn[k]) {
            vis[e] = vis[e ^ 1] = true;//考虑到可能有重边，这里我们标记边而不是点
            tarjan(k);
            vis[e] = vis[e ^ 1] = false;
            low[x] = min(low[x], low[k]);
            if (low[k] > dfn[x])can[id2[e]] = true;
        }
        else if (flag[k])low[x] = min(low[x], dfn[k]);
    }
    if (low[x] == dfn[x]) {
        while (st[*st + 1] != x) {
            flag[st[*st]] = false;
            --*st;
        }
    }
}

（点/边）双连通分量

强连通分量的概念是针对有向图的，对于无向图，我们称任意两点存在至少两条点不重复的路径的极大子图为点双连通分量，任意两点存在至少两条边不重复的路径的极大子图为边双连通分量。
每一个点双连通分量中没有割点，每一个边双连通分量中没有桥。
边双连通分量的求法比较简单，只需要去掉所有桥得到的就是边双连通分量。
点双连通分量模板：

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++tot;
    st[++top] = x;
    for (int e = p[x]; e; e = nt[e]) {
        int k = b[e];
        if (k == fa)continue;
        if (!dfn[k]) {
            tarjan(k, x);
            low[x] = min(low[x], low[k]);
            if (low[k] >= dfn[x]) {
                ++cnt;
                while (st[top + 1] != k)
                    ltk[st[top--]] = cnt;
                ltk[x] = cnt;
            }
        }
        else low[x] = min(low[x], dfn[k]);
    }
}

圆方树

在点双连通分量的概念下引出了圆方树。
树作为一种特殊的图，在处理时会比一般的图容易得多。如果我们能将一张无向图转化成树来进行处理将会更为方便，而圆方树就可以做到这一点。
在圆方树中，原图中的每一个点对应圆方树中的圆点，对每一个点双连通分量建立一个方点，由每一个方点向其连通分量内的圆点连边，对不属于任何连通分量的边单独建立方点连接边的两端，这样就构成了一棵圆方树。
如果原图是连通的，则最后建出来的圆方树就是一棵树。
根据上面的描述，圆方树的建立可以在求点双的过程中完成。

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++tot;
    st[++*st] = x;
    for (auto k : to[x]) {
        if (k == fa)continue;
        if (!dfn[k]) {
            tarjan(k, x);
            low[x] = min(low[x], low[k]);
            if (low[k] >= dfn[x]) {
                ++cnt;//创建方点
                while (st[*st + 1] != k) {
                    add(cnt, st[*st]);
                    --*st;
                }
                add(x, cnt);
            }
        }
        else low[x] = min(low[x], dfn[k]);
    }
}