本文主要讲解图的表示与经典算法在PAT解题中的算法选型、应用思路
联通分量问题
A1013 连通分量计数
数据结构：由于仅涉及节点编号，无其他信息，无向图的邻接表示用vector数组。
题意解析：敌人占领一个城市后，该城市与其他城市的道路均封闭，此时至少建几条路才能保证除该城市的所有城市保持联通。图中删去节点及邻路后，最少的建路方案是在剩余的n个连通分量之间建n-1条路，可以用DFS或并查集统计连通分量个数，不过并查集代码量略大一些
乀(ˉεˉ乀) Q：城市道路封闭是怎么考虑的呢？
(̿▀̿ ̿Ĺ̯̿̿▀̿ ̿) A：按理来说应该在图中删除该节点及所有邻边再去统计连通分量，但是修改了图结构。不删除的方法是统计连通分量时不统计这个节点，且DFS过程中无论哪个节点到达这个节点都返回，即没有这条邻边，相当于视其不存在
*=͟͟͞͞(꒪⌓꒪)** Q：我想的是新修路数=被占节点的相邻节点数-相邻节点之间的连通个数。而且觉得只看这K个节点就OK，没必要管全图。晕晕的~
(ง ˙o˙)ว A：你这个仅适用于这K个节点就是全图的情况，理由如下：如果去掉K图中的节点得到图K’仍然联通，这样看来就不需要建路了，但是你有没有想过，总体N除去K的子图本身也可能是不连通的呢？子图的不连通分量也要建的呀亲~所以每检查一个节点都要重新计算全图的连通分量个数。其次检测连接性用并查集吧，两两检测M个相邻节点之间的连接性要 $\scriptsize O(M^2)$，如果用DFS太慢了。哦对了，注意一下这道题目的节点默认标号是1-N，不要搞错
(⑉･̆-･̆⑉) Q：怎么求连通分量个数？
✧*。٩(ˊωˋ)و✧\。 A：每次DFS都访问一整个联通分量，这样遍历图中每个节点，依次检查图的每一个连通分量计数即可。访问过的节点都是已知连通分量中的，未访问的节点进行DFS标记就是将要标记的一个新的连通分量
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1001;
vector<int> g[maxn];
bool isVisited[maxn];
int cur;
void DFS(int s) {
if (s == cur) return;
isVisited[s] = true;
for (int &x : g[s])
if (!isVisited[x])
DFS(x);
}
int main() {
int N, M, K;
int s, t, cnt;
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < M; i++) {
scanf("%d %d", &s, &t);
g[s].push_back(t);
g[t].push_back(s);
}
for (int i = 0; i < K; i++) {
cnt = 0;
scanf("%d", &cur);
memset(isVisited, 0, sizeof(isVisited));
for (int i = 1; i <= N; i++) {
if (!isVisited[i] && i != cur) {
DFS(i);
cnt++;
}
}
printf("%d\n", cnt - 1);
}
return 0;
}最短路径问题
最短路径问题的理论讲解详见 ✈最短路径经典算法
A1003 最短路径计数、双尺度点权最优
堆优化的Dijkstra
算法选型：节点个数多于200，排除 $\scriptsize O(n^3)$ 的Floyd。路径长度无负权值，优选队列优化的Dijkstra，采用链式前向星实现
思路解析：题意为三个目标：
①寻找最短路径：Dijkstra策略从源节点s逐步松弛各边即可
②记录最短路径条数：rNum记录源节点到当前节点的最短路径条数。从源节点出发记条数为1开始扩散。
每次执行松弛代表找到从s→from→to的唯一一条最短路径，而s→from可能有多条相同长度的最短路径，所以s→from→to的最短路径数就是s→from的最短路径数。
dis[from]+length=dis[to]表示找到s→from→to的另一条不同的最短路径，此时在原有基础上又多了rNum[from]条最短路径
③记录最短路径中的最大点权和：每找到一条最短路径，都更新为该条最短路径的点权和，最短路径长度相同时，更新为更小的点权和，更新公式为 $\scriptsize \sum \limits_{i=s}^{to}Wi = \sum \limits{i=s}^{from}Wi + W{to}$
(╯>д<)╯ Q：链式前向星是什么神秘的数据结构？
(:3▓▒ A：链式前向星由一个数组(表示节点)和一个结构体数组(表示边)和一个边地址累计索引(表示新边插入结构体数组的索引)组成。节点数组：对应下标表示节点编号，值指向最后一次插入的边地址。结构体数组：保存边权、该条有向边指向的节点、同顶点其他出边的索引。添加的新边依次保存在边数组[索引]、边数组[索引+1]…边数组[索引+i]中。每插入一条新边使其指向上一次插入的边old，再让该出边的节点指向新边new，这样就实现了vertex→new→old，串起了节点出发的所有邻边，所以本质上是图的邻接表表示。值得注意的是本题是无向图，建图的时候一定要分别添加两个方向的边。
(˘•ω•˘)ง Q：为什么我的Dijkstra算法没写错，但是运行一次就退出了，有时候还运行不对？
⁽⁽ଘ( ˊᵕˋ )ଓ⁾⁾ A：在建图后、松弛操作时、第二尺度判断时埋打印点，拿输出结果和实例比对一下，方便调试找到问题。很可能的原因是运行算法前初始化出错了。一定不要忘记初始条件下：源节点到自身距离0、源节点出发的最短路径条数1、源节点本身即是最大点权和
#include <iostream>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxV = 500;
const int maxE = 1e5;
const int inf = 1e6;
int vertex[maxV], dis[maxV], done[maxV], inq[maxV];
int tSum[maxV], rNum[maxV], tNum[maxV];
int p = 0;
struct e {
int next;
int to;
int w;
} edge[maxE];
struct Cmp {
bool operator()(int a, int b) {
return dis[a] > dis[b];
}
};
priority_queue<int, vector<int>, Cmp> q;
void addEdge(int u, int v, int w) {
edge[p].to = v;
edge[p].w = w;
edge[p].next = vertex[u];
vertex[u] = p++;
}
void dijkstra(int s) {
q.push(s);
dis[s] = 0;
rNum[s] = 1;
tSum[s] = tNum[s];
while (!q.empty()) {
int v = q.top();
q.pop();
done[v] = 1;
inq[v] = 0;
for (int i = vertex[v]; ~i; i = edge[i].next) {
int w = edge[i].w;
int to = edge[i].to;
if (done[to]) continue;
if (dis[v] + w < dis[to]) {
dis[to] = dis[v] + w;
tSum[to] = tSum[v] + tNum[to];
rNum[to] = rNum[v];
if (!inq[to]) {
q.push(to);
inq[to] = 1;
}
}
else if (dis[v] + w == dis[to]) {
if (tSum[v] + tNum[to] > tSum[to])
tSum[to] = tSum[v] + tNum[to];
rNum[to] += rNum[v];
}
}
}
}
int main() {
int N, M, C1, C2;
int u, v, w;
scanf("%d %d %d %d", &N, &M, &C1, &C2);
for (int i = 0; i < N; i++)
scanf("%d", &tNum[i]);
fill(dis, dis + N, inf);
memset(vertex, -1, sizeof(vertex));
memset(done, 0, sizeof(done));
memset(inq, 0, sizeof(inq));
memset(tSum, 0, sizeof(tSum));
memset(rNum, 0, sizeof(rNum));
for (int i = 0; i < M; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
dijkstra(C1);
printf("%d %d\n", rNum[C2], tSum[C2]);
return 0;
}Dijkstra+DFS
来自晴神《算法笔记》的解法
A1030 保存最短路径+双尺度边权
算法选型：节点个数多于200，边长为城市距离无负权值，优选队列优化的Dijkstra，采用链式前向星实现
思路解析：题意为两个目标：
①找到最短路径中代价最小的那条。双尺度问题在A1003中详细解析过，按第一尺度找最短路径，按第二尺度记录更新最短路径的代价最小值。本题的第二尺度仅仅是将点权修改为边权。
②记录最短路径并打印。如果u节点的出边e使u→v松弛达到最短路径，就在v处保存前向的该节点，如果最短路径相同，就更新使第二尺度更小的前向节点u，如此从目标节点回溯到源节点即可找到该最短路径，倒序打印即可。
٩(*´◒`*)۶ Q：path保存的是倒序结果，那怎么正向打印节点呢？
<－biubiu－⊂(`ω´∩) A：栈或者递归咯！递归写起来简单，我们将递归置于操作之前，就能实现倒序操作的效果。递归边界是到达源节点，此时可以用path[s]=-1来判断。注意我们判断的是前序节点值path[i]，输出的是本层节点i
#include <iostream>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxV = 500;
const int maxE = 1e5;
const int inf = 1e6;
int dis[maxV], done[maxV], path[maxV], inq[maxV], cost[maxV];
int p = 0;
int Vertex[maxV];
struct Edge {
int next;
int to;
int w;
int c;
} e[maxE];
void addEdge(int from, int to, int w, int c) {
e[p].to = to;
e[p].w = w;
e[p].c = c;
e[p].next = Vertex[from];
Vertex[from] = p++;
}
struct Cmp {
bool operator()(int a, int b) {
return dis[a] > dis[b];
}
};
priority_queue<int, vector<int>, Cmp> q;
void dijkstra(int s) {
dis[s] = 0;
cost[s] = 0;
q.push(s);
while (!q.empty()) {
int from = q.top();
q.pop();
done[from] = 1;
inq[from] = 0;
for (int i = Vertex[from]; ~i; i = e[i].next) {
int to = e[i].to;
int w = e[i].w;
int c = e[i].c;
if (done[to]) continue;
if (dis[from] + w < dis[to]) {
dis[to] = dis[from] + w;
cost[to] = cost[from] + c;
path[to] = from;
if (!inq[to]) {
q.push(to);
inq[to] = 1;
}
}
else if (dis[from] + w == dis[to]) {
if (cost[from] + c < cost[to]) {
cost[to] = cost[from] + c;
path[to] = from;
}
}
}
}
}
void printPath(int d) {
int u = path[d];
if (~u) {
printPath(u);
printf(" %d", d);
}
else {
printf("%d", d);
return;
}
}
int main() {
int N, M, S, D;
int C1, C2, w, c;
scanf("%d %d %d %d", &N, &M, &S, &D);
fill(dis, dis + N, inf);
memset(Vertex, -1, sizeof(Vertex));
memset(path, -1, sizeof(path));
memset(done, 0, sizeof(done));
memset(cost, 0, sizeof(cost));
memset(inq, 0, sizeof(inq));
while (M--) {
scanf("%d %d %d %d", &C1, &C2, &w, &c);
addEdge(C1, C2, w, c);
addEdge(C2, C1, w, c);
}
dijkstra(S);
printPath(D);
printf(" %d %d", dis[D], cost[D]);
return 0;
}