正题

题目链接:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1038

题目大意

有n个点，输入点给出权值，其余点的权值为

$$C_i=sum_{i,jin E}W_{i,j}C_j-U_i$$

$C_i<=0$的话就不算
求输出层的权值

解题思路

求出一个点之前要求出到达他的所有点，所以我们用拓扑序计算就好了。

code

#include<cstdio>
#include<queue>
#define N 101
using namespace std;
struct node{
    int to,next,w;
}a[N*N];
int tot,n,m,in[N],ls[N],c[N],u,x,y,w;
queue<int> q;
void addl(int x,int y,int c)//加边
{
    a[++tot].to=y;
    a[tot].next=ls[x];
    a[tot].w=c;
    ls[x]=tot;
    in[y]++;
}
void bfs()
{
    while(!q.empty())
    {
        int x=q.front();
        if(c[x]>0)
        {
          for(int i=ls[x];i;i=a[i].next)
          {
              int y=a[i].to;
              in[y]--;
              c[y]+=a[i].w*c[x];//计算权值
              if(!in[y])//权值已经计算玩
                  q.push(y);
          }
        }
        else
        {
          for(int i=ls[x];i;i=a[i].next)
          {
              int y=a[i].to;
              in[y]--;
              if(!in[y])
                  q.push(y);
          }         
        }//为0不计算权值
        q.pop();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&u);
        if(c[i]) q.push(i);
        else c[i]-=u;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        addl(x,y,w);
    }
    bfs();
    bool flag=true;
    for(int i=1;i<=n;i++)
      if(!ls[i]) 
      {
        if(c[i]>0)
          printf("%d %dn",i,c[i]),flag=false;
      }
    if(flag) printf("NULL");
}

最后

以上就是时尚鞋垫为你收集整理的P1038-神经网络【拓扑排序】正题的全部内容，希望文章能够帮你解决P1038-神经网络【拓扑排序】正题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。