一、最短路
利用邻接表存图，无向图边的数量应当开$2m$。常常会开错，开成$2n$或是$m$
1. Dijkstra
Dijkstra基于贪心思想。
两个集合。$S$中的点是已经确定了到源点的最短路的，$V-S$是未知的。此时，$V-S$集合中的$d$全部都是由$S$得来的，换句话说，这些d值对应的最短路统统经过S内的点。
每一步从$V-S$中选择一个$d$最小的点$i$加入$S$中，即最短路得以确定。这个最短路一定是由$S$中的点构成的，并且是$S$中所能构成的最优的，因为它是由$S$中所有与它相邻的点松弛后得来的。利用反证法：如果它还不是最优的，则存在一个点$p$使得
dis[$i$->$p$->起点]<dis[$i$->起点] （1）
前者等于$dis(i,p)+d[p]$，后者等于$d[i]$。然而就目前状况来看，$d[i]<d[p]$，故（1）不成立。或曰$d[p]$还未确定，然而$d[p]$再松弛也不可能小于$d[i]$，因为它再要松弛也是被$i$或$d$比i更大的点松弛了。
因此有结论
dis[$i$->起点]≤dis[$i$->$p$->起点] （2）
也正是因为（2）式，使得Dijkstra只能用于边权非负的图。因为如果$dis(i,p)<0$就不一定满足了。
由于每次都是从一集合中选择$d$最小的元素，故可以用堆来优化。一个点可能会被多条边松弛，因此可能同时在堆中有好几个。此时需要剔除后来的。有一种不用done数组的方法，就是判断堆中存的d值是否大于数组中的d值。如果堆中的偏大则剔除。
以每个点为起点进行松弛，最多松弛成功$m$次。每一次加入堆的复杂度是$logn$。因此Dijkstra堆优化的复杂度是$O(mlogn)$
template_Dijkstra#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } struct node{ int u,d; }; int n,m,s,x,y,z,d[100010]; int head[100010],nxt[200010],to[200010],cost[200010],cnt; priority_queue <node> q; inline bool operator < (const node& a, const node& b){ return a.d > b.d; } inline void add(int u, int v, int w){ to[++cnt] = v; cost[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; } inline void dijkstra(int S){ for(int i = 0; i <= n+1; ++i) d[i] = 2000000000; d[S] = 0; q.push((node){S,0}); int u,D; while(!q.empty()){ u = q.top().u, D = q.top().d; q.pop(); if(D > d[u]) continue; for(int i = head[u]; i; i = nxt[i]){ if(d[u]+cost[i] < d[to[i]]){ d[to[i]] = d[u]+cost[i]; q.push((node){to[i],d[to[i]]}); } } } } int main(){ n = read(), m = read(), s = read(); for(int i = 1; i <= m; ++i){ x = read(), y = read(), z = read(); add(x,y,z); } dijkstra(s); for(int i = 1; i <= n; ++i){ printf("%d ",d[i]); } return 0; }
2. Bellman-Ford / SPFA
针对Dijkstra无法处理的负权情况。
显然，最短路上一定不存在环。那么最短路一定是一个生成树状物。因此最多包含$n-1$条边。从每个点出发松弛一次称为一次迭代。可以通过迭代$n-1$来求得最短路。因为我们已经考虑到了所有可能边数的最短路，因此显然正确。这就是Bellman-Ford。复杂度显然$O(nm)$
然而每一次都从所有点出发松弛没有必要，有些点可能在上一次并没有被松弛，即$d$没有改变，那就没有必要再去做一次。换句话说，我们发现只有上一轮被松弛了的点才可能去松弛别人。因此我们用一个队列来保存上一轮被松弛的点。这就是SPFA。当然，最坏情况依然是$O(nm)$。
从很多方面，SPFA都和BFS很像。而BFS可以来求无权图的最短路，因为无权图中边数即路径长度——第一次松弛时的最短路一定最优。而当图有了边权，第一次松弛以后可能会被再次松弛，因为有可能边数更多，路径长度却更小。这使得一个点可能会重复进队，这是和BFS不同的。
SPFA也因此还需要一个bool数组来判断一个点是否在队中。如果已经在队中，再去进队就没有意义了。和Dijkstra不同，这里的队列只保存了点的编号，而$d$是与点的编号对应的，因此在松弛时其实已经将队中的点的$d$修改到更优了。
关于负环，很显然如果迭代次数超过$n-1$即有负环。然而在SPFA中好像不是那么容易计算迭代次数的，因为第几次迭代都一股脑儿在队列里了。那么就判断松弛次数吧，反正肯定不会错。另外，有向图中某点出发可能无法到达负环。
template_SPFA与负环#include <cstdio> #include <algorithm> #include <cstring> using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } int T,n,m,x,y,z,h,t,d[4010],q[4000010],inq[4010],dep[4010]; int head[4010],nxt[8010],to[8010],cost[8010],cnt; inline void init(){ memset(head,0,sizeof(head)); memset(nxt,0,sizeof(nxt)); memset(to,0,sizeof(to)); memset(cost,0,sizeof(cost)); cnt = 0; } inline void add(int u, int v, int w){ to[++cnt] = v, cost[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; } inline bool SPFA(int S){ memset(d,0x3f,sizeof(d)); memset(inq,0,sizeof(inq)); memset(dep,0,sizeof(dep)); d[S] = h = t = 0; q[++t] = S; int u; while(h < t){ ++h; u = q[h]; inq[u] = 0; for(int i = head[u]; i; i = nxt[i]){ if(d[u]+cost[i] < d[to[i]]){ d[to[i]] = d[u]+cost[i]; dep[to[i]] = dep[u]+1; if(dep[to[i]] > n-1) return 1; if(!inq[to[i]]){ inq[to[i]] = 1; q[++t] = to[i]; } } } } return 0; } int main(){ T = read(); while(T--){ init(); n = read(), m = read(); for(int i = 1; i <= m; ++i){ x = read(), y = read(), z = read(); add(x,y,z); if(z>=0) add(y,x,z); } if(SPFA(1)) printf("YE5 "); else printf("N0 "); } return 0; }
有了以上两者，最短路问题就得以解决。然而最短路的题目难在建模。以下是几个例子。
显然这是一个有向图，看上去很可以DP。然而这道题是有环的，又不能一次使解定型。因此DP挂了。
由此这道题变成了图的问题。和DP类似，令状态（可以状压）为点，补丁为边进行建模。跑一跑dijkstra就可以了。然而点非常多，因此不要建图，而是建隐式图。
给出一系列不等关系，问其总和的最大/最小值。解决这类问题的被称为差分约束系统。其本质是，不等式相加仍成立。因此令图中的一条边作为一个不等式。由此，一条路径的长度就是其两个端点需要满足的不等关系。然后再考虑解集的性质，如果是大于号，那么就应该求最长路。注意用spfa判负环。
差分约束的题目关键是要充分利用题目的条件将其转化到图中。例如，当题目要求所有数都为正数时，这也是一个必须满足的条件。常常加入一个虚拟点向所有点连1的边来解决。
这道题还有一个玄学优化，就是虚拟点连边时要倒序，非常玄学。
二、图的深度优先遍历
对于图的DFS，常常利用DFS树来理解。这样子图就转化成了树。
1. 割点/割边
对于无向图的每一个连通分量，如果删掉一个点$u$就不再连通，则称其为割点。
无向图的DFS树中，边不是树边就是返祖边。显然，对于一个点$u$，如果其子树中存在一个节点必须通过$u$来到达$u$的祖先，那么$u$一定是割点。而一个点可以不用经过$u$的，必定是存在返祖边直接飞到$u$以上去了。因此，问题转化为判断每个点的子树中，是否存在返祖边不能到达$u$的祖先的点。只要存在一个，那么$u$就是割点。
因此我们设置数组$low[i]$表示节点$i$以及它的子树中的点最上能到上哪儿。关于如何来量度这个上，我们设置数组$dfn[i]$表示节点$i$第一次被搜索到的次序（时间戳）。在DFS树中，一个节点的子节点时间戳必定大于其祖先的时间戳。由此，只要存在一个子节点$v$满足$$low[v] leq dfn[u]$$那么$u$即为割点。那么余下的问题就是如何求$low$了，除了求出$low[v]$的最小值，别忘了还有自己的返祖边所能达到的最小值。
根节点是特殊情况。因为它没有祖先，因此只需要判断子节点个数就可以了。
我们发现，求割点的复杂度和纯DFS没有区别，$O(n+m)$。
于是割边就显得自然而然了。只要将条件改为$$low[v] < dfn[u]$$就说明$u-v$是割边
template_割点#include <cstdio> #include <algorithm> #include <cstring> using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } int n,m,x,y,dfs_clock,cnt_cut; int head[20010],nxt[200010],to[200010],cnt; int dfn[20010],low[20010],cut[20010]; inline void add(int u, int v){ to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt; } void dfs(int u, int Fa){ int v,cnt_son=0; low[u] = dfn[u] = ++dfs_clock; for(int i = head[u]; i; i = nxt[i]){ v = to[i]; if(v == Fa) continue; if(!dfn[v]){//树边,dfn可以充当vis数组 ++cnt_son; dfs(v,u); low[u] = min(low[u],low[v]); if(low[v] >= dfn[u]) cut[u] = 1;//满足条件 } else low[u] = min(low[u],dfn[v]);//返祖边 } if(Fa == -1) cut[u] = (cnt_son>1);//注意如果不满足要cut[u]=0 } int main(){ n = read(), m = read(); for(int i = 1; i <= m; ++i){ x = read(), y = read(); add(x,y), add(y,x); } for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i,-1); for(int i = 1; i <= n; ++i) cnt_cut += cut[i]; printf("%d ",cnt_cut); for(int i = 1; i <= n; ++i) if(cut[i]) printf("%d ",i); return 0; }
2. 点-双/边-双
留坑
3. 强连通分量(SCC)
反证法在OI里的运用真的是极其广泛……
边是单向的，因此图的连通性是个问题。
每个点仅在一个SCC中。反证。
在DFS树中，一个节点$u$是可以到达所有子节点的。因此只要子节点能够回到$u$或$u$的祖先，就能达成“互相可达”。因此$u$以及所有能到达$u$或$u$以上的节点能构成一个强连通分量。
一个强连通分量一定在一个子树中。Tarjan算法思想是：在DFS树中，找出每个SCC中的最高点，以确定每个SCC。我们称这个最高点为强连通分量的根。
既然是强连通分量，就要求其内每个点都能够到达根。如果有的点能到达的最高点低于根，一定不属于这个强连通分量，因此要把它割掉。
DFS结束时，判断一个点是否是根，如果是就取出子树中剩余的点组成一个强连通分量。
强连通分量可以用来给有向图缩点，使它变成DAG。值得注意的是缩点建图的时候要判断自环。
感觉还是有点乱……明天理理思路再更。
template_强连通分量void dfs(int u){ int v; push(u); dfn[u] = low[u] = ++dfs_clock; for(int i = head[u]; i; i = nxt[i]){ v = to[i]; if(!dfn[v]){ dfs(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ ++scc_cnt; while(top > 0){ sccno[st[top]] = scc_cnt; val[scc_cnt] += a[st[top]]; --top; if(st[top+1] == u) break; } } }
· Codeforces 999 E. Reachability from the Capital 【1900】
给一张有向图。问要能从一个源点s到达其余所有点最少添加几条有向边。
这个问题肯定要缩点之后来考虑，因为一个强连通分量内的点是没有连通性问题的。于是问题转化为一张DAG。我们先考虑全都右边相连的情况（没有孤立的）。此时s肯定能到达后代，而无法到达祖先。需要加的边下界为入度为0的点的个数，因为如果一个点连入度都为0那么s肯定无法到达，而一条边只能给一个点加一个入度。我们考虑能不能做到这个下界：只需要从s向所有入度为0的点连边。
再考虑孤岛的情况，从一座岛向另一座岛，我们也只需要从s向入度为0的点连边就行了。
因此问题的答案就是入度为0的点的个数（不能包括s）
4. 2-SAT
和差分约束一样，2-SAT问题是利用图论建模来解决的一类问题。只需要把图的意义搞明白就差不多了。
所谓SAT问题，全称satisfiebility，即可满足性。问题的具体内容是：有$n$个$bool$变量$x_i$，要满足若干个条件，例如一个条件是【$x_1=1$且($x_3=0$或$x_4=0$)】。求出一种满足所有条件的$x$的取值。
2-SAT问题的意思是，每个命题仅由两个部分构成。也就是说，条件必须是类似【$x_1=1$或$x_5=0$】这个形式的。
下面假定所有条件都是【$x_i=a$或$x_j=b$】这种形式的。
我们可以这样来理解这个条件：如果$x_i = ¬a$，则$x_j=b$；如果$x_j = ¬b$，则$x_i=a$。
我们考虑建一张图。对于每一个变量$x_i$可以有两种状态，令节点$i$表示$x_i=1$，节点$i+n$表示$x_i=0$。如果要满足状态$s_1$则必须满足$s_2$，那么就连接$s_1->s_2$。如此，对于【$x_i=a$或$x_j=b$】这个条件，就需要连接$x_i = ¬a$到$x_j=b$，再连接$x_j = ¬b$到$x_i=a$。
这张图的意义是什么？标记图上的一个点，代表选择这种状态。从这个点延伸出去的边表示如果这个状态要满足，那么必须满足其他这些。而这些点又连出去……也就是说，如果我选择一个点$u$，那么所有$u$能到达的点都必须满足。
因此我们可以这样来求解：考虑每一个$x_i$。先默认$x_i=0$不满足，则我们从$¬i$出发，如果到达了$i$就矛盾了。显然我们不能标记$¬i$。因此$x_i=1$
然而，试想如果$i$也会到达$¬i$？那此问题显然无解！因此，如果$i$与$¬i$相互可达，即在同一个强连通分量中，则问题无解。
反之，如果对于任何一个点都不存在这种情况，则问题一定有解（不会矛盾）。
如果方案可以随意，显然我们有一种更简单的做法：对于每一个$i$与$¬i$，我们都选择拓扑序（缩点完成后成为DAG）大的那个，这样肯定是不会矛盾的。
template_2SAT#include <cstdio> #include <algorithm> #include <cstring> const int MAXN = 2000010; const int MAXM = 2000010; using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } int n,m,I,A,J,B,top,dfs_clock,scc_cnt,low[MAXN],dfn[MAXN],st[MAXN],sccno[MAXN]; int head[MAXN],nxt[MAXM],to[MAXM],cnt; inline void add(int u, int v){ to[++cnt] = v; nxt[cnt] = head[u]; head[u] = cnt; } void dfs(int u){ int v; st[++top] = u; dfn[u] = low[u] = ++dfs_clock; for(int i = head[u]; i; i = nxt[i]){ v = to[i]; if(!dfn[v]){ dfs(v); low[u] = min(low[u],low[v]); } else if(!sccno[v]){ low[u] = min(low[u],dfn[v]); } } if(dfn[u] == low[u]){ ++scc_cnt; while(top > 0){ sccno[st[top]] = scc_cnt; --top; if(st[top+1] == u) break; } } } int main(){ n = read(), m = read(); for(int i = 1; i <= m; ++i){ I = read(), A = read(); J = read(), B = read(); add(I+((A^1)^1)*n,J+((B)^1)*n); add(J+((B^1)^1)*n,I+((A)^1)*n); } for(int i = 1; i <= 2*n; ++i){ if(!dfn[i]){ top = 0; dfs(i); } } for(int i = 1; i <= n; ++i){ if(sccno[i] == sccno[i+n]){ printf("IMPOSSIBLE"); return 0; } } printf("POSSIBLE "); for(int i = 1; i <= n; ++i){ printf("%d ",sccno[i]<sccno[i+n]); } return 0; }
我在考虑这点时提出了这样的一个问题：有没有可能a与-a存在于一条链上，而b与-b可以同时到达这条链呢？（在a之前到达）。我已经有了答案：不可能存在这种情况。因为假若b能到a，则-a能到-b，则-b,a,-a在同一个强连通分量中了。
如何利用2-SAT建模：需要考虑布尔变量是什么，条件是什么。
那么在这道题里，每条边可以选择在圆内或在圆外，显然一条边是一个布尔变量。需要满足的条件是任意两条边都不能交叉。然后利用强连通分量判断可行性即可。