反向建图+拓扑排序
零、复习拓扑排序
\(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\)
求拓扑有两种形式
-
求字典序最小：建正图，找最小的进行更新，正序输出。
-
求编号最小：建反图，找最大的进行更新，倒序输出。
\(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\)
总结：字典序最小与编号最小是两回事，用不同的方法实现！
思路：在当前步骤，在所有入度为\(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;
}
#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;
}