模拟赛 - 图论专项（一）#

$10 / 400$

T1 机器人擂台赛 (ranking, CF645D)#

拓扑序唯一性。即，在拓扑排序过程中，不能出现多个入度为 $0$ 的节点，否则无法判断机器人级别。

二分答案，当q.size() > 1时，拓扑序不唯一，缩小范围，直到找到唯一拓扑序为止，否则输出 -1。

待补。

T2 最近奇偶数对 (parity, CF1272E)#

BFS，反向建图。

待补。

T3 逃离螺旋迷宫 (maze, COCI2008, P6399)#

建图， $a$ ，跑 Dijkstra。待补。

T4 最优星际贸易 (COCI2012/2013 Final, HIPERPROSTOR)#

关于 SPFA，它死了。因此不补。

算法#

广度优先搜索 BFS#

因为种种原因之前没有学习BFS，今天被模拟题重创才开始恶补。

例题 P5318 查找文献

核心思想：

将起点先入队。此时q.front()为起点。
重复以下操作：
取出队列最前端的点，遍历所有与它相邻的点。如果没有访问过，打标记并入队。遍历结束后弹出最前端的点。

1
//链式前向星存图
2
void bfs(int u){
3
  queue<int> q;
4
  q.push(u);
5
  v[u] = 1;
6
  ans2.push_back(u); //存储路径
7
  while(!q.empty()){
8
    int fro = q.front();
9
    for(int i = head[fro]; i; i = e[i].nxt){
10
      int to = e[i].to;
11
      if(!v[to]){
12
        q.push(to);
13
        v[to] = 1;
14
        ans2.push_back(to);
15
      }
16
    }
17
    q.pop();
18
  }
19
}

Complete Code

拓扑排序 (Topological Sort, Kahn)#

例题 P4017 最大食物链计数

BFS的变种。仅适用于 DAG (有向无环图)，否则会在环中打转，陷入死循环。

“事实上，拓扑排序就是将一个图变化为一个线性序列的过程。故，我愿称之为降维打击。” ——Aw顿顿

核心思想：

在建边的时候维护每个点的入度。

1
for(int i = 1; i <= m; i++){
2
    int u, v;
3
    cin >> u >> v;
4
    add(u, v);
5
    ind[v]++;
6
    }

扫一遍点，找到入度为 $0$ 的点。入队。
重复操作：

取出此点并出队，将其放入拓扑序数组，遍历此点的相邻点并将它们的入度 $-1$ 。 (直观地说，就是删除此点)
当队列为空时，说明所有节点都已进入拓扑序数组。

1
bool topsort() {
2
    queue<int> q;
3
    int cnt = 0;  //输出顶点的个数
4
    for (int i = 1; i <= n; i++)
5
        if (ind[i] == 0) q.push(i);
6
    while (!q.empty()) {
7
        int x = q.front();
8
        q.pop();
9
        A[++cnt] = x;
10
        for (int i = 0; i < G[x].size(); i++) {
11
            int y = G[x][i];
12
            ind[y]--;
13
            if (ind[y] == 0) q.push(y);
14
        }
15
    }
16
    return cnt == n; //true:无环  false:有环
17
}

时间复杂度 $O(E + V)$ 。

Complete Code

Dijkstra 单源最短路#

例题 P4779 【模板】单源最短路径（标准版）

一种贪心算法，求带正权图中单源点到其他所有节点的最短路。

核心思想：

初始化 dis[s] = 0，其余顶点的 dis均为inf。
在所有未标记顶点中找出 dis 值最小的顶点 x ，并标记。
对 x 的所有未标记邻接点 y 进行松弛操作。
重复 2、3 操作 $n$ 次，直至所有顶点都被标记。

1
void Dijkstra(){
2
    for(int i = 1; i <= n; i++)
3
        dis[i] = inf;
4
    dis[s] = 0;
5
    d.v = s, d.w = 0; q.push(d);
6
    while(!q.empty()){
7
        int u = q.top().v;
8
        q.pop();
9
        if(vis[u]) continue;
10
        vis[u] = 1;
11
        for(int i = head[u]; i; i = e[i].next){
12
            if(dis[e[i].to] > (long long)dis[u] + e[i].val){
13
                dis[e[i].to] = dis[u] + e[i].val;
14
                d.v = e[i].to, d.w = dis[e[i].to]; q.push(d);
15
            }
16
        }
17
    }
18
}