经过一晚上的不懈努力,创造出了一个很烂的拓扑排序的板子
这是精简版
using ll = long long;
struct tsort {int n;std::vector<std::vector<int>>g, w;std::vector<int>r, c, dp,f;std::queue<int>q;tsort(int n_) {n = n_;g.resize(n + 1);w.resize(n + 1);r.resize(n + 1);c.resize(n + 1);f.resize(n + 1);dp.resize(n + 1);}void add(int x, int y, int v = 0) {//有向边g[x].push_back(y);//值w[x].push_back(v);//入度r[y]++;//出度c[x]++;}ll all(int x=0, ll M=0, int s=0) {ll ans = 0;if(s)q.push(s);else {for (int i = 1; i <= n; i++) {//if (x && i != x) {dp[i] = -1e9;if (r[i] == 0)q.push(i);}else if (M&&r[i] == 0) {q.push(i);f[i] = 1;}}}while (!q.empty()) {//int x = q.front();//q.pop();//for (int i = 0; i < g[x].size(); i++) {//int j = g[x][i];//if(M)f[j] = (f[j] + f[x]) % M;if(s)dp[j] = std::max(dp[j], dp[x] + w[x][i]);r[j]--;//if (r[j] == 0) {if (M&&c[j] == 0) {ans = (ans + f[j]) % M;continue;}q.push(j);//}}}return ans;}
};int main() {int n, m;std::cin >> n >> m;tsort t(n);while (m--) {int x, y;std::cin >> x >> y;t.add(x, y);}std::cout << t.all(0, 80112002,0);return 0;
}
传入第一个参数用于去除其它重复的入度为0的路径,传入第三个参数,用于计算从该点到其它的点的最长路径,两者通常结合在一起使用,传入第二个参数,用于计算入度为0出度为0的路径有多少个,第二个参数是模数.其它两个参数要设为0
下面这个是不省略的版本
using ll = long long;
struct tsort {int n;std::vector<std::vector<int>>g, w;std::vector<int>r, c, dp,f;std::queue<int>q;tsort(int n_) {n = n_;g.resize(n + 1);w.resize(n + 1);r.resize(n + 1);c.resize(n + 1);f.resize(n + 1);dp.resize(n + 1);}void add(int x, int y, int v = 0) {//有向边g[x].push_back(y);//值w[x].push_back(v);//入度r[y]++;//出度c[x]++;}//固定起点,去重bool dedup(int x) {//如果起点入度不为0,返回false//if (r[x])return false;for (int i = 1; i <= n; i++) {//if (i != x) {dp[i] = -1e9;if (r[i] == 0)q.push(i);}}while (!q.empty()) {//int x = q.front();//q.pop();//for (int i = 0; i < g[x].size(); i++) {//int j = g[x][i];//r[j]--;//if (r[j] == 0)q.push(g[x][i]);//}}return true;}//计算所有入度为0,出度为0的路径,M是模数ll pathsum(ll M= 80112002) {ll ans = 0;for (int i = 1; i <= n; i++) {if (r[i] == 0) {q.push(i);f[i] = 1;}}while (!q.empty()) {int x = q.front();q.pop();for (int i = 0; i < g[x].size(); i++) {int j = g[x][i];r[j]--;f[j] = (f[j] + f[x]) % M;if (r[j] == 0) {if (c[j] == 0) {ans = (ans + f[j]) % M;continue;}q.push(j);}}}return ans;}void work(int s) {q.push(s);while (!q.empty()) {int x = q.front();q.pop();//该点所对应的所有路径for (int i = 0; i < g[x].size(); i++) {dp[g[x][i]] = std::max(dp[g[x][i]], dp[x] + w[x][i]);if (!--r[g[x][i]])q.push(g[x][i]);}}}};int main() {int n, m;std::cin >> n >> m;tsort t(n);while (m--) {int x, y;std::cin >> x >> y;t.add(x, y);}std::cout << t.all(0, 80112002,0);return 0;
}
这个板子就略显臃肿
当然,如果你只想计算一条合理的拓扑序列,你可以将所有参数设为0,且将入度为0的点放入答案即可.