拓扑排序
例题:P1038 神经网络
当某一节点对子节点的处理,需要等待其所有父节点对自身的处理完成再进行时,可以考虑使用拓扑排序.
编写拓扑排序时,给节点添加记录入边和出边数量的变量,这里用in,out表示.当一个节点in为0时,此节点为初始节点,out为0时,为末节点.
每次寻找in为0的节点,此时该节点已被处理完成,可以处理其子节点,处理子节点时,将子节点的in-1,即该节点的一个父节点对自身的处理已完成.之后反复迭代,处理完成的节点不再处理,直到所有节点都处理完.此时末节点为完成态.
#include<bits/stdc++.h> #define MAXN 105 using namespace std; struct TO { int id,w; }; struct NODE { int c,u; int in,out; list<TO>to; int vis; }; NODE node[MAXN]; int n,p,x,y,z; int main() { cin>>n>>p; for(int i=1;i<=n;i++){ cin>>node[i].c>>node[i].u; node[i].c-=node[i].u; } for(int i=1;i<=p;i++){ cin>>x>>y>>z; node[x].to.push_back({y,z}); node[x].out++; node[y].in++; } queue<int>q; for(int i=1;i<=n;i++){ if(node[i].in==0){ q.push(i); node[i].c+=node[i].u; } } while(!q.empty()) { int now=q.front();q.pop(); node[now].vis=1; if(node[now].c>0){ for(auto& i:node[now].to){ node[i.id].c+=node[now].c*i.w; node[i.id].in--; } } if(q.empty())for(int i=1;i<=n;i++){ if(node[i].vis==0&&node[now].in==0){ q.push(i); } } } int jug=0; for(int i=1;i<=n;i++){ if(node[i].out==0&&node[i].c>0){ cout<<i<<" "<<node[i].c<<endl;; jug=1; } } if(jug==0)cout<<"NULL"<<endl; return 0; }拓扑排序详解与实现(转载)
