「随笔」简单的总结

树剖时,如果把边附着到点上,注意$id[x] + 1$。
最小生成树的处理方案,通常基于“非加这条边不可”。
如果不行,还有一种就是“用非树边来替换树边”。
新遇见的二分的两种策略:
最短路,单调队列。
二分重在一个“限制”,有些时候会把“限制的条件”赋值为1。
单调队列长于维护区间最小值。
单调栈则长于维护“第一个$xx$某元素的位置”。
多维度,维护具体信息的前缀和很常用。(区间众数)
考场上用并查集来离线还是太复杂了(大雾
定一动一的思路依然很常见。

「学习笔记」图论

图论总结

魔法森林

tag: SPFA

题目大意

$n$点$m$边无向图,每条边两个权值$a_i, b_i$,寻找一条$1 \rightarrow n$的路径,使得路径上$max{a_i} + max{b_j}(i, j \in [1, m])$最大。

解法

考虑用$SPFA$动态加点。对$a$进行排序,依次加入,然后用$SPFA$动态加点跑$SPFA$。

关键代码

每次加入一条边。
就向一个新的图里加入这条边,然后把边的两端点$push$到$queue$里。自行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
q.push(1);
dis[1] = 0;
v[1] = 1;

inline void Addedge(int u, int v, int a, int b) {
static queue<int> q;
static int v[N];
while (!q.empty()) q.pop();
addedge(u, v, a, b);
q.push(u);
q.push(v);
v[u] = v[v] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
v[u] = 0;
for (int i = head[u]; ~i; i = nxt[i]) {
int to = ver[i], c = edge[i];
if (dis[to] > max(dis[u], c)) {
dis[to] = max(dis[u], c);
if (!v[to])
v[to] = 1,
q.push(to);
}
}
}
}

备注

$SPFA$动态加点本身是个骚操作,这个骚操作下还有一个$hash$检测的骚操作。可以新建一个边权,作为$hash$的$rand$值。每一次加边,跑出新的$hash$的$dis$和原图的$dis$,可以检测这条边是否影响路径。主要是放不放心的问题,其实也没啥用。
还有不少可以使用此方法的题,比如说LG1462。虽然我用此方法并没有$A$。

路径统计问题

双倍经验,最短路计数问题

tag: 最短路

题目大意

$n$点$m$边有向图,问$1 \rightarrow n$有多少条最短路。

题解

类似$floyd$求最短路径条数。
但是这道题对$SPFA$的理解要求略高。
简单阐述一点,平时容易忽略的。
最短路的目标是,满足任意一个$dis[to] \leq dis[u] + v$,即三角形不等式。
$floyd$的思想是,遍历所有的三角形。这里我再谈谈$floyd$的理解,即为什么$k$一定要放在外面。
引出问题,明明我们可以写成$for \ i, j, k$,为什么非要写成$for \ k, i, j$?
为什么,路径计数的时候就必须写成前者,最短路径计数就必须写成后者?
首先看我们的更新,$f[i][j] = min(f[i][j], f[i][k] +f[k][j])$。
也就是说,用$f[i][k], f[k][j]$的最短路径来更新$f[i][j]$。前提是,这$n^3$次遍历中,一定有一次,$f[i][k], f[k][j]$已经取到最小值了。然后用这个最小值更新$f[i][j]$。但是,在$for \ i, j, k$的情况下。我们在更新$f[i][j]$之后,不会再动$f[i][j]$,可是如何保证在遍历到$f[i][j]$的时候,所有的最短路已经被求出?即所有的点均满足三角形不等式?万一存在一个$k$,$f[i][k]$并不是最短路呢?那么$f[i][j]$就并没有被$i \rightarrow k, k \rightarrow j$的最短路更新。我们已经证明了$for \ i, j, k$的循环顺序是错误的了。

(已修改,之前的证明有问题)
对于$f[k][i][j]$,表示在$i \rightarrow j$的路径,不经过编号超过$k$的路径的最短路是。对于$k - 1$到$k$,只用新关注经过$k$的点,问题就来了,在经过$k$的所有路径中,存不存在一条路径$\leq f[k - 1][i][j]$。于是我们扫描$i, j \in [1, n]$,转移如下:$f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j])$。$Q.E.D.$,虽然我并不认为这个证明方法很优雅。
填最开始提出的问题,为什么路径计数是$for \ i, j, k$。详见矩阵乘法定义。

然后证明$SPFA$。首先需要证明$Bellman \ Ford$。复杂度是$O(|V||E|)$。过程是遍历所有的边,然后循环所有的点。需要证明,在整个遍历结束后,一定满足任意的$dis[u] + v \geq dis[to]$。我们考虑遍历完第$k$条边之后,哪些点完成了$dis$的计算。假如说图中的边权全是1,最坏的情况,距离点$1$为$k$的点就被完成了计算。换句话说,第一次遍历后,1点直接相邻的点就被更新了,第二次遍历后,1点直接相邻的点又向外拓展了一层。由于图的“层数”不超过$|V|$。所以在第层数次拓展之后,所有的点一定已经被更新了。$Q.E.D.$。然后回到$SPFA$的证明。

$SPFA$存在一个松弛操作,复杂度玄学。相同的道理。之前提到的三角形不等式,$dis[u] + v \geq dis[to]$。一切最短路算法都必须围绕这一点展开。在$SPFA$彻底完成之后,所有的三角形不等式必须被满足,也就是$dis[to]$一定会在$dis[u]$是最短路后被更新。在$SPFA$的$queue$中,装的实际上是所有的被更新$dis[u]$的点,但是被更新之后不一定是最小值。$SPFA$的$vis$中,装的不是“被更新过的点”,而是在$queue$中的点。对于$u$被更新过最小值后,需要尝试把$u$加入$queue$之中,这时有两种情况,$u$已经在$queue$中了,那么下一次取出更新的时候,$to$一定是被$u$的最短路更新的。如果不在,那么$to$一定会被加入后取出的$u$更新一次。所以$dis[to]$一定会在$dis[u]$是最短路后被更新。

回到这道题的最短路计数。当我们用$cnt[u]$更新之后,为什么需要$cnt[u] = 0$?$u$或许会再次从$queue$中被取出,下一次的路径条数不一定满足上一次的,也就是我们清空的那一次$cnt[u]$。而在下一次更新到$u$的时候,会有别的点帮助我们更新$cnt[u]$,如果保留这一次的$cnt[u]$,下一次的$cnt[u]$就是不同长度的路径的条数,然而我们要的仅仅是最短路径的长度,不需要之前的半成品。所以我们在用$cnt[u]$重新更新$cnt[to]$的时候,实际上是在用新的长度的路径进行更新。

参考:https://blog.csdn.net/ljhandlwt/article/details/52096932 (我放弃的证明方法,质疑正确性)
https://blog.csdn.net/qq512028505/article/details/72453761 (我采用的证明方法)

代码

未AC,不知道为啥。
这题要去重边,还有各种问题,暂时放弃了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
int n, m, tot, head[N], g[N][N],
ver[N * N], nxt[N * N],
edge[N * N], dis[N], cnt[N], vis[N];
queue<int> q;
inline void addedge(int u, int v, int c) {
ver[tot] = v;
edge[tot] = c;
nxt[tot] = head[u];
head[u] = tot++;
}
int main() {
memset(head, -1, sizeof head);
scanf("%d%d", &n, &m);
for (int i = 1, u, v, c; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &c);
g[u][v] = min(g[u][v], c);
// addedge(u, v, c);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (g[i][j]) addedge(i, j, g[i][j]);
memset(dis, 0x3f, sizeof dis);
dis[1] = 0, cnt[1] = 1, vis[1] = 1;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
if (u == n) continue;
for (int i = head[u]; ~i; i = nxt[i]) {
int to = ver[i], v = edge[i];
if (dis[to] == dis[u] + v)
cnt[to] += cnt[u];
if (dis[to] > dis[u] + v) {
cnt[to] = cnt[u];
dis[to] = dis[u] + v;
if (!vis[to] && cnt[u])
q.push(to), vis[to] = 1;
}
}
cnt[u] = 0; // ...
}
if (dis[n] == 0x3f3f3f3f)
puts("No answer");
else
cout << dis[n] << " " << cnt[n];
}

备注

这道题涉及的知识点也很多,后面会慢慢拓展。
比如说$NOIP2017 d1t3$。

Cow Relays

tag: floyd, 快速幂

题目大意

给出$n$点$m$边无向图,求$S \rightarrow E$经过$k$条边的最短路,$k \leq 100$。

题解

倍增$floyd$板题。我们向$floyd$加入矩阵的思维。定义矩阵乘法为$floyd$的计算。具体内容我会在后面的代码中给出。假如说初始矩阵能够表示一个联通图(无任何意义,也不是特殊情况,只是方便解释一点)。那么在$floyd$第一次之后,我们计算出的$f$矩阵是一个完全图,$f[i][j]$可以简单看做$i \rightarrow j$经过$1$条边,$i \rightarrow j$的最短路。任何$(i, j)$都可以这么认为。假如,我是说假如哦,将这个矩阵按照$floyd$进行平方。$f^2$的意思是?$f^2[i][j]$表示$i \rightarrow j$经过2条边的最短路是。已经提到过,$f$本身视作一个完全图,那么$f[i][j] = f_1[i][k] + f_2[k][j]$。因为$i \rightarrow k, k \rightarrow j$直接就是最短路了,那么$i \rightarrow j$就表示$i \rightarrow k, k \rightarrow j$之后的最短路,这俩都是经过一条边的,那么$i \rightarrow j$一定是最少经过两条边。显而易见的,$f^k[i][j]$表示$i \rightarrow j$经过$k$条边的最短路。用快速幂计算即可。

关键代码

1
2
3
4
5
6
7
8
9
Matrix operator * (Matrix x) {
Matrix b(n, n);
memset(b.a, 0x3f, sizeof a);
for (int k = 1; k <= n; ++i)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
b[i][j] = min(b[i][j], *this -> a[i][k] + x.a[k][j]);
return b;
}

后面是矩阵快速幂模板,略了。

备注

类似的题目:
BZOJ1297LG1119

软件补丁问题

tag: SPFA

题目大意

懒得概括。

题解

是网络流,但是其实就是个$BFS$。或者状压$dp$也可以解。
我们将一个状态看做$SPFA$中的一个点,每个状态向下一个状态的连边就是所有可以打的补丁的集合。每个补丁的权值是1,也就是边权是1。建图跑$SPFA$即可。

这道题的重点不在这,是在把每个状态看成$SPFA$中的一个点。然而,我发现我写了个裸$BFS$。$BFS$当成$SPFA$能够一定程度的简化思维,毕竟图上的思考能够帮助整理逻辑。可以说是一个$SPFA$的建模吧?类似的,简单状压$dp$也可以用类似的,$SPFA$建模的方式水过去。比如说这个:https://www.luogu.org/problemnew/show/P2831。

好吧,总结一下,这道题的关键就在于把状态看成图上的点,而这个操作的写法基本等同于$BFS$,可以说是殊途同归了。但是这个思路方法可以一定程度地减少思维难度。以上。

魔法猪学院

tag: Dijkstra

从这道题能够延伸出一个大的版块,也就是$SPFA$中的动态规划的思想,但是这些在解决完这道题之后再说w

题目大意

$n$点$m$边有向图,从$1 \rightarrow n$的所有路径中,第$k$短的是。

题解

如果这道题需要像之前路径计数那样一个一个证明的话,大概我会死掉的。
堆优化的$Dij$有一个性质,在第$k$次从堆中取出到达某个点的值的时候,这个值是到这个点第$k$长的路径。证明我懒得搞,记着就对了。看到这个结论,我恍然大雾,这,跑$Dij$模板不就对了么。$TLE$。
为什么会$T$?简单分析一下的话,我们花费太多的时间在计算$[1, n - 1]$的某个长度的路径上。我们需要尽量减少对于$[1, n - 1]$的状态的取出。在堆上的优化有啥,$A*$。我们尽量多取出关于$n$的状态。也就是说,估价函数必须偏爱$n$。如何偏爱,距离$n$近的优先取出。

备注

我用类似的方法卡过$NOIP2017D1T3$,但是并没有成功,多卡了10分。
果然难题大多只有一种解法。

逛公园

tag: 最短路, DP

题目大意

$n$点$m$边有向图,令$1 \rightarrow n$的最短路是$d$,求长度$\leq d + k$的,$1 \rightarrow n$的路径个数。$k \leq 50$。

题解

我没有理解到为什么要建反图,或者说考场上我想不到为啥要建立反图。
状态设计很简单$f[i][j]$,到$i$,比$dis[i]$多$j$的边的路径个数。
然后剩下的先咕咕咕,等我想清楚再说。

宝藏

tag: DFS

题解

略微奇怪,lyd说这个解法是错的。
暂时咕咕咕,因为我不清楚为什么延展出来是一棵树。

关键代码

1
2
3
4
5
6
inline void dfs(int k) {
for (int i = 0; i < n; ++i) if(k & (1 << i))
for (int j = 0; j < n; ++j)
if(!(k & (1 << j)) && f[k | (1 << j)] > f[k] + edges[i][j] * d[i] && edges[i][j] != 0x3f3f3f3f)
f[k | (1 << j)] = f[k] + edges[i][j] * d[i], d[j] = d[i] + 1, dfs(k | (1 << j));
}

货车运输

tag: 生成树, 树链剖分

题解

这道题蛮板的。
首先,生成树的,一下就能想到。
简述生成树的使用吧,这类$i \rightarrow j$的最大值问题,通常都涉及生成树。(或许也会涉及$tarjan?$)。
然后树链剖分模板套上去。$AC$。

旅行

tag: 二分, 并查集