警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「笔记」day4 - 图论

:warning:注意:这是ZROI集训的源笔记,其中有很多缺失和遗漏以及无法看懂的部分,大家就不要看了吧。

以下是原笔记:


搜索

DFS

二分图判定

dfs即可。\(1\)相邻\(2\)\(2\)相邻\(1\)

不是二分图则会染色矛盾。

时空阵

先不考虑距离为\(m\)

考虑bfs的分层。

\(dp_{i,j,k}\)\(i\)层,\(j\)个点,第\(i\)\(k\)个点的方案数。

枚举第\(i+1\)层的点数\(x\)

                         标号    层内   跨层

转移:\(dp_{i+1,j+x,x}=dp_{i,j,k}\cdot\binom{n-j}x\cdot 2^\binom x2\cdot(2^k-1)^x\)

现在考虑距离为\(m\)

\(dp_{m,j,k}\cdot \frac k{n-1}\)\(m\)层,\(j\)个点,第\(m\)\(k\)个点。\(k\over n-1\)是因为概率和对称性

每个k元组出现的概率是相等的

再考虑剩下的\(n-j\)个点连边。

它们可以内部连边,并且只能和第\(m\)层(k个点)连边

               内部   外部

所以\(dp_{m,j,k}\cdot\frac k{n-1}\cdot 2^\binom {n-j}2\cdot 2^{k(n-j)}\)

欧拉回路

正常版

图必须联通,小心孤立点

充要条件:

欧拉路:\(0\)\(2\)个奇点。

欧拉回路:全是偶点。

证明略

"回溯算法"

算法证明略

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int u, int c) { // O(n+m)
void dfs(int u) {
while (!e[u].empty()) {
int v = e[u][e[u].size()-1].first;
int id = e[u][e[u].size()-1].second;
e[u].pop_back(); // O(1) 减小循环代价
if (vis[id]) continue; // 有向图删了
vis[id] = 1; // 有向图删了
dfs(v);
ans.push_back(id);
// auto it=--e[u].end();
}
}

高端版

最少路径数覆盖整张图?

先往\(2k\)个奇点之间加\(k\)条边让奇点消失。然后跑欧拉回路,然后拆边,会拆成\(k\)条路径。

然后这题就成了结论题。

例题

1

?

2

将区间中的\(l\)\(r\)构点建边,然后判跑一遍欧拉回路。

  1. 如果有欧拉回路,那么方向是→就将区间设为\(1\),如果是←就设为\(-1\)

  2. 没有欧拉回路就把点全部升序排序,然后\(12\)\(34\)\(56\)......的连边。

然后去掉加的边按方向设置\(1\)\(-1\)

证明略

Dijkstra

每次将最短路最短的未确定点确定,然后再将新确定点相邻的点更新,直到跑完为止。

可以利用小根堆将复杂度优化至\(O((n+m)\log n)\)

平板电视大法好

稠密图用naive算法不要优化!不要优化!!不要优化!!!

Bellman-Ford

\(O(nm)\)

不怕负权边。

\(dis[u][i]\)走不超过\(i\)步到\(u\)

方程:\(dis[u][i]=min(dis[u][i-1], dis[v][i-1]+w[v][u])\)

华容道

并没有

\(dis(x,y,dir)\)表示把\((x,y)\)\(dir\)方向移动。

将空格移到\((x,y)\)附近需要\(c\)的代价,可以预处理。

多点最短路

HDU 6166

简单版

考虑无向图。

先把所有\(k\)中的点的\(dis\)设为\(0\),然后松弛时记录父节点。

然后枚举所有边,如果边的两边是来自不同的源点,那么用\(dis[u]+dis[v]+w[u][v]\)更新答案。

正常版

?????

定义\(f(u,v)\)\(u\)点集到\(v\)点集的最短路。

然后弄一个超级源和一个超级汇,一个连整个\(u\),一个连整个\(v\),然后算一下最短路即可。

然后做\(2log_2n\)跑出对于\(u,v\in S,u\ne v\)\(f(u,v)\)

复杂度\(nlog^2n\)

强连通分量

如果一张图中所有的点对\((u,v)\)中的\(u,v\)可以互相到达,那么张图是强连通的。

  • 树边:从父亲跑到儿子的边。
  • 返祖边:从晚辈跑到祖辈的边。
  • 前向边:从祖辈跑到晚辈的边。(不包括树边)
  • 横叉边:乱连的边。

Low Case:树边+返祖边\((u,v)\)

那么\(u\)\(v\)的路径全部在同一个强连通分量里。

首先弄一个时间戳,也就是dfn

定义low[i]代表\(i\)子树能通过返祖边和横叉边能够到的的最浅的点(跳出子树为止)。

如果dfn[i]=low[i],那么\(i\)子树再也跳不上去了,所以\(i\)子树组成一个强连通分量。

注意!如果你通过横叉边往上跑的时候跑到的是一个完整的强连通分量,那么Congratulations,这个作废。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int u) {
dfn[u] = low[u] = ++ind; // index
ins[u] = 1; // instack(没形成强连通分量的栈)
st[++top] = u;
for (int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], dfs(low[v]));
} else if (ins[v]) { // 不是强连通分量
low[u] = min(low[u], dfn[v]); // 可以换成low[v]
}
}
if (dfn[u] == low[u]) {
++cnt;
while (1) {
bel[st[top]] = cnt; // belong
ins[st[top]] = 0;
if (st[top--] == u) break;
}
}
}

缩点

缩点后一定是个DAG

最大半联通子图

先缩点。

如果图有分叉就会发现不可达,然后求最长链即可。

于是每个点都有了权值\(w[i]\)

最后就直接\(dp[u]=\max(dp[v]+w[v]), (u,v)\in E\)