【题解】Luogu P1038 神经网络拓扑排序

小咪咪 2023-08-17 16:49 91阅读 0赞

topsort 板(?)题

显然，题目要求从入度为零的点遍历到出度为零的点，想到用拓排

另如果是输入层，那么u\[i\]为1或0都没有关系，一定会激活

同时处理出度便于输出

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int inf=1e9+7;
     6 const int maxn=1e4+10;
     7 inline int read(){
     8     int x=0,f=1;
     9     char c=getchar();
    10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    12     return x*f;
    13 }
    14 struct edge{
    15     int to,nxt,w,from;
    16 }e[maxn*2];
    17 int head[maxn],cnt,r[maxn],p[maxn];
    18 int n,m,t,c[maxn],u[maxn],fl;
    19 inline void add(int from,int to,int w){
    20     e[++cnt].from=from;e[cnt].to=to;e[cnt].w=w;
    21     e[cnt].nxt=head[from];head[from]=cnt;
    22     ++r[to];++p[from];
    23 }
    24 void topsort(){
    25     queue<int>q;
    26     int x,v;
    27     for(int i=1;i<=n;i++){
    28         if(!r[i])q.push(i);
    29     }
    30     while(!q.empty()){
    31         x=q.front();q.pop();
    32         for(int i=head[x];i;i=e[i].nxt){
    33             v=e[i].to;--r[v];
    34             if(c[x]>0)c[v]+=c[x]*e[i].w;
    35             if(!r[v])q.push(v);
    36         }
    37     }
    38 }
    39 int main(){
    40     n=read();m=read();
    41     for(int i=1;i<=n;i++){
    42         c[i]=read();u[i]=read();
    43         if(c[i]==0)c[i]-=u[i];
    44     }
    45     for(int i=1;i<=m;i++){
    46         int x,y,z;x=read();y=read();z=read();
    47         add(x,y,z);
    48     }
    49     topsort();
    50     for(int i=1;i<=n;i++){
    51         if(c[i]>0&&p[i]==0){
    52             printf("%d %d\n",i,c[i]);
    53             fl=1;
    54         }
    55     }
    56     if(!fl)printf("NULL\n");
    57     return 0;
    58 }
    59 }
    60 signed main(){
    61   gengyf::main();
    62   return 0;
    63 }

转载于:https://www.cnblogs.com/gengyf/p/11603914.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/cae29c93703543d582bc42dc82889762.png