反向建图+拓扑排序

零、复习拓扑排序

\(HDU\) \(3342\) \(Legal\) \(or\) \(Not\)

【正图，普通拓扑排序】

题意：给出\(n\)人的编号为 \(0\)到\(n-1\),再给出\(m\)个关系。\(A\)和\(B\)，\(A\)是\(B\)的老师。问这些关系是否存在矛盾，即不能存在\(A\)是\(B\)的老师，\(B\)是\(C\)的老师，而\(C\)是\(A\)的老师。

思路：很容易发现，存在矛盾的样例的图一定存在环。而 拓扑排序是判断是否有环的很好算法。即如果从队列中取出的点不等于\(n\)，就一定存在环。

注：不能由队列是否为空来判断，当\(n - 2, 1->2, 2->1\)时队列也为空，当这是有环的。只有当每个点取出，才可以确定没有环。

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = N << 1;
int in[N]; // 入度
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool solve(int n) {
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (in[i] == 0) q.push(i);

    int cnt = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();

        ++cnt;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            in[j]--;
            if (in[j] == 0) q.push(j);
        }
    }
    return cnt == n;
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    while (cin >> n >> m && n) {
        // 多组测试数据，一定要注意两个初始语句！
        memset(h, -1, sizeof h);
        idx = 0;
        memset(in, 0, sizeof in);

        while (m--) {
            int u, v;
            cin >> u >> v;
            in[v]++;
            add(u, v); // 建正图
        }
        bool ans = solve(n);
        puts(ans ? "YES" : "NO");
    }
    return 0;
}

\(HDU\) \(2647\) \(Reward\) 奖励

题意：老板发奖金，每个工人至少\(888\)元，而有些工人存在着要求，\(a\)和\(b\)，\(a\)要求他的奖金要比\(b\)高。给你\(n\)个工人，编号为\(1\)到\(n\)，\(m\)个要求，求老板总共最低需要给这些工人多少奖金。不能满足他们的要求就输出\(-1\)。

思路：不能满足要求，即存在环。当满足要求时，最小的\(b\)得\(888\)，向上依次加\(1\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = N << 1;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int num[N]; // 记录每个工人的最终获取多少奖金
int n, m;
int in[N], ans;

int toposort() {
    queue<int> q;
    int cnt = 0; // 出队列的节点个数
    ans = 0;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);

    while (q.size()) {
        int u = q.front();
        q.pop();
        cnt++;
        ans += num[u]; // 出队时，累加出队人员的奖金数量

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            in[j]--;
            if (in[j] == 0) {
                q.push(j);
                num[j] = num[u] + 1; // 需要表示反向图指定的节点比源节点的奖金大1
            }
        }
    }
    if (cnt != n) ans = -1;
    return ans;
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> m) {
        // 初始化链式前向星
        memset(h, -1, sizeof h);
        idx = 0;
        memset(in, 0, sizeof in);
        for (int i = 0; i <= n; i++) num[i] = 888; // 每个人最少888元

        while (m--) {
            int u, v;
            cin >> u >> v;
            add(v, u); // 小的向大的建图
            in[u]++;
        }
        printf("%d\n", toposort());
    }
    return 0;
}

一、基本认识

• 当有向图需要求多个点到一个点的最短距离时
• 除了使用多元最短路的方法还可以通过反向建边转化为单源最短路
• 顾名思义，将边反向

二、反向建边方法

• 用邻接表存图时(用堆优化版\(dijkstra\)跑最短路时适用

int dist[2 * N];

// 链式前向星，因为是两份图，所以啥啥都是两份
int h[2 * N], ne[2 * M], e[2 * M], w[2 * M], idx;
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);         // 正图
    add(b + n, a + n, c); // 反图
}

• 翻转邻接矩阵

void over(int n){//翻转
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            swap(g[i][j], g[j][i]);
}

三、什么类型的题目需要反向建图 ？

1、多点到一点的最短距离，需要反向建图

邮递员送信

题目描述
有一个邮递员要送东西，邮局在节点 \(1\)。他总共要送 \(n-1\) 样东西，其目的地分别是节点 \(2\) 到节点 \(n\)。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 \(m\) 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 \(n-1\) 样东西并且最终回到邮局最少需要的时间。

输入格式
第一行包括两个整数，\(n\) 和 \(m\)，表示城市的节点数量和道路数量。

第二行到第 \((m+1)\) 行，每行三个整数，\(u,v,w\)，表示从 \(u\) 到 \(v\) 有一条通过时间为 \(w\) 的道路。

输出格式
输出仅一行，包含一个整数，为最少需要的时间。

input    output  83
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = N << 1;
typedef pair<int, int> PII;

int n, m, s;
int dist[2 * N];

// 链式前向星，因为是两份图，所以啥啥都是两份
int h[2 * N], ne[2 * M], e[2 * M], w[2 * M], idx;
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(int s) {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆
    q.push({0, s});

    while (q.size()) {
        auto t = q.top();
        q.pop();

        int u = t.second;
        if (st[u]) continue;
        st[u] = 1;

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                q.push({dist[j], j});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);         // 正图
        add(b + n, a + n, c); // 反图
    }

    int res = 0;
    // 单源最短路，就是从1出发，到达其它n-1个点的最短距离
    dijkstra(1);
    for (int i = 1; i <= n; i++) res += dist[i];

    // 从n-1个节点，返回1号节点，就是多源最短路
    // 通过建反图，将多源最短路转化为单源最短路
    // 建反图时，所以节点号+n处理，这样1号节点就变成1+n号节点,其它n-1个节点向1号节点的多源最短路就变成了
    // 从1+n~ [2+n,3+n,...,n+n]的最短路径了
    dijkstra(1 + n);
    for (int i = 1 + n; i <= 2 * n; i++) res += dist[i];

    printf("%d\n", res);
    return 0;
}

\(P3916\) 图的遍历
题目描述

给出 \(N\) 个点，\(M\) 条边的有向图，对于每个点 \(v\)，求 \(A(v)\) 表示从点 \(v\) 出发，能到达的编号最大的点。

输入格式

第 \(1\) 行 \(2\) 个整数 \(N,M\)，表示点数和边数。

接下来 \(M\) 行，每行 \(2\) 个整数 \(U_i,V_i\)，表示边 \((U_i,V_i)\)。点用 \(1,2,\dots,N\) 编号。

输出格式

一行 \(N\) 个整数 \(A(1),A(2),\dots,A(N)\)。

样例输入

4 3
1 2
2 4
4 3

样例输出

4 4 3 4

提示

• 对于 \(60\%\) 的数据，\(1 \leq N,M \leq 10^3\)。
• 对于 \(100\%\) 的数据，\(1 \leq N,M \leq 10^5\)。

解题思路
一开始大家的思路应该就是单纯的\(dfs\)但是我们注意到\(n,m\)的范围到了\(10^5\) ,这时\(O(N^2)\) 的暴力是过不去的,于是我换了个思路，按题目来每次考虑每个点可以到达点编号最大的点，不如考虑较大的点可以反向到达哪些点。

循环从\(N\)到\(1\)，则每个点\(i\)能访问到的结点的\(A\)值都是\(i\)。

每个点访问一次，这个\(A\)值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了，这样做的同时也避免了每次都要更新状态值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N << 1;

int n, m;
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int res[N];

void dfs(int u, int val) {
    if (res[u]) return; // 如果已经标记过，不用重复标记
    res[u] = val;       // 没有标记过，就标记一下

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!res[j]) dfs(j, val);
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(b, a);
    }

    for (int i = n; i >= 1; i--) dfs(i, i);
    for (int i = 1; i <= n; i++) cout << res[i] << ' ';
    return 0;
}

2、对于要求编号小的靠前输出这类题需要反向建图

\(Q\):为什么这样的要求需要反向建图 ?
比如说：有\(1,2,3\) 共\(3\)个数，要求 \(3\) 在 \(1\) 前面输出(对 \(2\) 没有要求)

如果没有反向建图的话，会造成输出 \(2, 3, 1\)这样的错解(实际上应该输出 \(3,1,2\) ...)

详细步骤
对于给定顺序：
\(6 -> 4 -> 7\) (对于这一行，要求先输出\(6\)，再输出\(4\)，最后输出 \(7\))
\(3 -> 9 ->2\) (同上)
\(5 ->1 ->8\) (同上)

这样我们反向建图，每次都处理（比较）入度为 \(0\) 的点
\(6 <- 4 <- 7\)
\(3 <- 9 <- 2\)
\(5 <- 1 <- 8\)

这样我们先比较 \(7,2,8\) 这一列（ 入度为 \(0\) 嘛），大的肯定是最后输出(要求小的先输出)

因此 \(ans[1] = 8\) ,把 \(8\) 剔除出去，与 \(8\) 相连的点的入度 \(-1\)
\(6 <- 4 <- 7\)
\(3 <- 9 <- 2\)
\(5 <- 1\)
此时入度为 \(0\) 的点有 \(7,2,1\) ，然后再把最大的剔除出去

因此 \(ans[2] = 7\)，与 \(7\) 相连的点的入度 \(-1\)
\(6 <- 4\)
\(3 <- 9 <- 2\)
\(5 <- 1\)

此时入度为 \(0\) 的点有 \(4,2,1\) ，然后再把最大的剔除出去

因此 \(ans[3] = 4\) 与 \(4\) 相连的点的入度 \(-1\)。

反复执行上述步骤，直至处理完全部入度为 \(0\) 的点（ 可能有环。。。）

最后得到 \(ans[1] = 8 ; ans[2] = 7 ;ans[3] = 4 ; ans[4] = 6 ;ans[5] = 2 ; ans[6] = 9 ;ans[7] = 3 ;ans[8] = 1 ; ans[9] = 5\)

此时，我们再反向输出，即可以得到答案
\(5, 1, 3, 9, 2, 6, 4, 7, 8\)

求拓扑有两种形式

• 求字典序最小：建正图，找最小的进行更新，正序输出。

  \(HDU\) \(1285\)

• 求编号最小：建反图，找最大的进行更新，倒序输出。

  \(HDU\) \(4857\) 逃生

  牛客网 菜肴制作

\(Q\):这两种题目有什么不同呢?

我们发现前一道是要求 字典序最小优先输出 即可 后面一道却是要求 编号最小优先输出！

对于这张图，字典序最小优先输出 是 1 3 4 2

\(BUT\), 编号最小优先输出 是 1 4 2 3

思路:

首先这道题 给定了两个数之间的位次关系 ,那么显然是需要用到 拓扑排序 的.

输出不可行的方法 也十分简单,只要 使用拓扑排序判断一下有没有形成环 即可,因为假设形成了环了话,那么我们的这个环就不存在一个点的入度为\(0\),那么这个点就不会加入到\(bfs\)中,最终的答案队列中的数就不够\(n\)个了,所以此时直接输出impossible!即可。

那么接下来的主要解决问题就是 如何保证越小的值越在前面 这个问题了.首先我们肯定会想到使用贪心输出字典序最小的序列,但是遗憾的是,这个贪心显然是错误的.举个反例:

\(4\)种菜肴，限制为 \(<2,4> <3,1>\) 那么字典序最小的是 \(2,3,1,4\) 但题目要求的最优解是 \(3,1,2,4\) 这\(4\)种菜肴，所以我们直接使用贪心做是不行的.

贪心：\(2\)在\(4\)前，\(3\)在\(1\)前，而\(2、3\)无顺序关联，\(4、1\)无顺序关联，按字典序的话，就是\(2、3、1、4\)
题目要求:先考虑\(1\)，需要在\(3\)后，即\(3、1\)，然后考虑\(2\),需要在\(4\)前,就是\(3、1、2、4\)
总结：字典序最小与编号最小是两回事，用不同的方法实现！

\(HDU\) \(1285\) 确定比赛名次

思路：在当前步骤，在所有入度为\(0\)的点中 输出编号最小的。考虑用\(BFS\)实现，修改\(BFS\)的拓扑排序程序，把普通队列改为优先队列\(Q\)。在\(Q\)中放入度为\(0\)的点，每次输出编号最小的结点，然后把它的后续结点的入度减一，入度减为\(0\)的再放进\(Q\)，这样就能输出一个字典序最小的拓扑排序。

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

bool g[N][N]; // 邻接矩阵
int in[N];    // 入度
int n, m;     // n个顶点，m条边

// 小顶堆
priority_queue<int, vector<int>, greater<int>> q;

/*
4 3
1 2
2 3
4 3

1 2 4 3
*/
void toposort() {
    // 所有入度为零的节点入队列，是拓扑序的起始节点
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);

    int cnt = 0;
    while (q.size()) {
        int u = q.top();
        q.pop();
        cnt++; // 又一个节点出队列

        // 输出拓扑序
        if (cnt != n)
            cout << u << " ";
        else
            cout << u << endl;

        for (int i = 1; i <= n; i++)
            if (g[u][i]) {
                in[i]--;
                if (!in[i]) q.push(i);
            }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(g, 0, sizeof g);
        memset(in, 0, sizeof in);

        while (m--) {
            int x, y;
            cin >> x >> y;
            if (g[x][y]) continue; // 防止重边
            g[x][y] = 1;           // 设置有关联关系
            in[y]++;               // 入度+1
        }
        toposort(); // 拓扑序
    }
    return 0;
}

牛客网 菜肴制作

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010, M = N << 1;
int in[N]; // 入度数组

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void solve() {
    memset(in, 0, sizeof in); // 入度
    memset(h, -1, sizeof h);  // 初始化链式前向星
    idx = 0;

    priority_queue<int> q;         // 优先队列大顶堆
    map<pair<int, int>, int> _map; // 使用红黑树保存已经添加过关系的数，防止出现重边
    vector<int> ans;
    int n, m;
    cin >> n >> m; // n个菜，m个关系
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (!_map[{x, y}]) { // 防止重复建边
            _map[{x, y}] = 1;
            add(y, x); // 反向建图
            in[x]++;   // 记录入度
        }
    }
    // 入度为零的入队列
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);

    // Topsort
    while (q.size()) {
        int u = q.top(); // 序号大的先出来，然后倒序输出
        q.pop();
        ans.push_back(u); // 记录出队顺序
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            in[j]--;
            if (!in[j]) q.push(j);
        }
    }
    if (ans.size() != n)
        cout << "Impossible!";
    else
        for (int i = n - 1; i >= 0; i--) cout << ans[i] << ' ';
    cout << endl;
}

signed main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

\(HDU\) \(4857\) 逃生【拓扑排序反向建图】

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = N << 1;

int n, m, ans[N], al;
int in[N];

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void topsort() {
    priority_queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);

    while (q.size()) {
        int u = q.top();
        q.pop();
        ans[al++] = u;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            in[j]--;
            if (in[j] == 0) q.push(j);
        }
    }
}
void solve() {
    cin >> n >> m;
    al = 0, idx = 0;
    memset(h, -1, sizeof h);

    while (m--) {
        int u, v;
        cin >> u >> v;
        add(v, u);
        in[u]++;
    }
    topsort();
    for (int i = al - 1; i >= 0; i--) {
        cout << ans[i];
        if (i != 0)
            cout << ' ';
        else
            cout << endl;
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}