题目内容

P1038

大意:模拟一个神经网络,神经网络分层,每个节点有一个初始状态或者阈值,每个节点当状态大于0时向下层节点传递信息。

解题思路

注意读题

  • 输入神经元的入度一定为0
  • 输出神经元的出度一定为0
  • 边权可能为负
  • 如果没有大于0的输出层,记得输出NULL

因此这个图一定是个DAG,C_i的状态又需要上一个点的状态求解,故使用拓扑排序。

分析公式:

\begin{aligned}
C_i&=\sum_{(j,i\in E)}W_{j,i}C_j-U_i\
C_i+U_i&=\sum_{(j,i\in E)}W_{j,i}C_j
\end{aligned}

因此非输入层的节点的权值相当于要减去一个常数,故U_i没有必要存储,读入时判断即可

拓扑排序的思路仍然是判断这个点的入度并入队

代码:

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct Edge//边的结构体
{
    int from,to,dist;
};

const int maxn=106;
vector<Edge> g[maxn];//vector存图
int n,p,c[maxn],ind[maxn],oud[maxn];
//n,p见题意,ind存储入度,oud存储出度
queue<int> q;//拓扑排序时使用的队列

void ins(int u,int v,int w)//插入边
{
    g[u].push_back((Edge){u,v,w});
    return;
}

void topo()//拓扑排序函数
{
    while(!q.empty())//当队列不为空时
    {
        int now=q.front();
        q.pop();//记得pop
        for(auto &i:g[now])//C++11新特性
        {
            int to=i.to;
            if(c[now]>0)//如果当前节点的c值大于0
                c[to]+=c[now]*i.dist;//说明信息会继续传递下去,注意+=
            if(!--ind[to])//如果删掉该边后入度为0
                q.push(to);//那么你也可以入队了
        }
    }
    return;
}

int main()
{
    scanf("%d %d",&n,&p);
    for(int i=1;i<=n;i++)
    {
        int u;
        scanf("%d %d",&c[i],&u);
        if(c[i])//如果c[i]大于0,则一定是输入层
            q.push(i);
        else
            c[i]-=u;//否则对u进行预处理
    }
    for(int i=1;i<=p;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ins(u,v,w);
        ind[v]++,oud[u]++;//对入度出度进行处理
    }
    topo();//记得排序
    bool flag=0;
    for(int i=1;i<=n;i++)
    {
        if(c[i]>0 && oud[i]==0)
        {
            printf("%d %d\n",i,c[i]);
            flag=1;
        }
    }
    if(!flag)
        printf("NULL\n");//不要忘输出NULL
    return 0;
}

反思

读题真的挺重要的,几乎掉的所有坑都是不仔细读题分析造成的

emm

图论。。。多练吧

最后修改日期:2020年2月2日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。