拓扑排序的英文名是 Topological sorting。
拓扑排序要解决的问题是给一个图的所有节点排序。
拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。 ——OI-WiKi
拓扑排序是在 DAG（有向无环图） 中每次选则入度为 0 的节点加入队列，并删除与这个节点相连的边，重复执行此操作。
这样做的作用是后面加入队列的节点一定不依赖于前面的节点，因此拓扑排序有无后效性，可以用于 dp。
也可以用于判环，当队列为空时若还有边则该图有环。
例题 1：
思路很简单，d[] 用于存储最长距离，rd[] 用于存储入度。
第一遍代码：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue <int> q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
d[i] = -0x7f7f7f7f7f7f7f7f;
}
while(m--){
scanf("%d%d%d", &u, &v, &w);
rd[v]++;
f[u][v] = 1;
g[u][v] = w;
}
d[1] = 0;
q.push(1);
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 1; i <= n; i++){
if(f[t][i]){
d[i] = max(d[i], d[t] + g[t][i]);
rd[i]--;
if(rd[i] == 0){
q.push(i);
}
}
}
}
if(d[n] == -0x7f7f7f7f7f7f7f7f){
puts("-1");
}else{
printf("%lld\n", d[n]);
}
return 0;
}
45 分，下了一组数据，发现有重边的情况。。。。
略改输入部分代码。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue <int> q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
d[i] = -0x7f7f7f7f7f7f7f7f;
}
while(m--){
scanf("%d%d%d", &u, &v, &w);
if(!f[u][v]) rd[v]++;
f[u][v] = 1;
g[u][v] = max(g[u][v], w);
}
d[1] = 0;
q.push(1);
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 1; i <= n; i++){
if(f[t][i]){
d[i] = max(d[i], d[t] + g[t][i]);
rd[i]--;
if(rd[i] == 0){
q.push(i);
}
}
}
}
if(d[n] == -0x7f7f7f7f7f7f7f7f){
puts("-1");
}else{
printf("%lld\n", d[n]);
}
return 0;
}
然并卵，还是 WA。
原因是其他与目标路径无关的点没有入队，导致部分点最长路已经确定了，但入度不为 0，解决方法就是在 1 入队之前先把其他入度为 0 的点入队，A 之。
最终代码：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1505;
int n, m;
int u, v, w;
int t;
long long d[N];
bool f[N][N];
int g[N][N];
int rd[N];
queue <int> q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
d[i] = -0x7f7f7f7f7f7f7f7f;
}
while(m--){
scanf("%d%d%d", &u, &v, &w);
if(!f[u][v]) rd[v]++;
f[u][v] = 1;
g[u][v] = max(g[u][v], w);
}
for(int i = 2; i <= n; i++){
if(rd[i] == 0){
q.push(i);
}
}
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 1; i <= n; i++){
if(f[t][i]){
rd[i]--;
if(rd[i] == 0){
q.push(i);
}
}
}
}
d[1] = 0;
q.push(1);
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 1; i <= n; i++){
if(f[t][i]){
d[i] = max(d[i], d[t] + g[t][i]);
rd[i]--;
if(rd[i] == 0){
q.push(i);
}
}
}
}
if(d[n] == -0x7f7f7f7f7f7f7f7f){
puts("-1");
}else{
printf("%lld\n", d[n]);
}
return 0;
}
其实可以跑 SPAF
例题 2：
类似板子题，一开始只需要将所有入度为 0 的点入队，没有奇怪数据。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int n, m, x, y, t;
int rd[N], d[N];
vector <int> g[N];
queue <int> q;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
d[i] = -0x7fffffff;
}
while(m--){
scanf("%d%d", &x, &y);
rd[y]++;
g[x].push_back(y);
}
for(int i = 1; i <= n; i++){
if(rd[i] == 0){
q.push(i);
d[i] = 1;
}
}
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 0; i < g[t].size(); i++){
d[g[t][i]] = max(d[g[t][i]], d[t] + 1);
rd[g[t][i]]--;
if(rd[g[t][i]] == 0){
q.push(g[t][i]);
}
}
}
for(int i = 1; i <= n; i++){
printf("%d\n", d[i]);
}
return 0;
}
总结：
- 要注意题目对于图的描述，是否有重边或自环；
- 注意数据范围，最长的距离是等于 \((n-1) \cdot d_{max}\)；
我可真是蒟蒻，连拓扑排序都写不清楚。