P1038 神经网络（60）

2023-11-19 12:10:37

ps:我真的是无语了，敲了两个半小时结果还只有60分qwq

觉得自己的思路好像没什么bug，但是程序输出就是有几个点W掉T掉（好像时间复杂度也不是很高？）

难过嘤嘤嘤(╥╯^╰╥)

好啦，回归正题，来讲一下我的思路以及我的艰难踩雷过程....

题目背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

题目描述

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

神经元〔编号为111）

图中，X1X3是信息输入渠道，Y1Y2 是信息输出渠道，C1表示神经元目前的状态，Ui 是阈值，可视为神经元的一个内在参数。

神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，CiC_iCi服从公式：（其中nnn是网络中所有神经元的数目）

Ci=∑(j,i)∈EWjiCj−UiC_i=\sum\limits_{(j,i) \in E} W_{ji}C_{j}-U_{i}Ci=(j,i)∈E∑WjiCj−Ui

公式中的WjiW_{ji}Wji（可能为负值）表示连接jjj号神经元和iii号神经元的边的权值。当 CiC_iCi大于000时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为CiC_iCi。

如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（CiC_iCi），要求你的程序运算出最后网络输出层的状态。

输入格式

输入文件第一行是两个整数n(1≤n≤100)n(1 \le n \le 100)n(1≤n≤100)和ppp。接下来nnn行，每行222个整数，第i+1i+1i+1行是神经元iii最初状态和其阈值（UiU_iUi），非输入层的神经元开始时状态必然为000。再下面PPP行，每行由222个整数i,ji,ji,j及111个整数WijW_{ij}Wij，表示连接神经元i,ji,ji,j的边权值为WijW_{ij}Wij。

输出格式

输出文件包含若干行，每行有222个整数，分别对应一个神经元的编号，及其最后的状态，222个整数间以空格分隔。仅输出最后状态大于0的输出层神经元状态，并且按照编号由小到大顺序输出。

若输出层的神经元最后状态均为 000，则输出 “NULL”。

输入输出样例

输入 #1

输出 #1

3 1
4 1
5 1

其实根据题意我们很快就可以发现这道题好像只要模拟一下就可以（所以题解中的拓扑？什么鬼？），我们发现，其实原式可以改写成

$C[i]+U[i]=\sum\limits_{(j,i)\in E}{W_{(j,i)}}*C[j]

所以我们一开始不需要管u的值，只需要在循环结束时直接减去u即可。

核心代码，两层for循环判断邻接表中是否存在与当前节点相连的节点，然后直接将wi和cj相乘即可，最后把所有的满足条件的点加起来，就是当前节点的c值（好像是在把公式翻译了一遍....）

但是注意：这里其实有一个坑点（莫问偶是咋知道滴），题目中要求输入层神经元的c必须为1，但是上面的算法却是更改c值的！所以我们要加一层特判，来避免失误

#include<bits/stdc++.h>
using namespace std;

struct noed {
    int opt,u,c;
};

struct N {
    int c,u;
};

int chu[102];
int ru[102];

N a[102];

int w[102][102];
int n,m;

int ans[102];
bool vis[102];

int fa[102][102];
int num[102];

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i].c >>a[i].u ;
    }

    for(int i=1; i<=m; i++) {
        int x,y,z;
        cin>>x>>y>>z;
        w[x][y]=z;
        w[y][x]=z;
        chu[x]++;
        ru[y]++;
    }

    for(int i=1; i<=n; i++) {
        int ans=a[i].c ;
        for(int j=1; j<=n; j++) {
            if(ans!=0) break;
            else if(!vis[a[j].c ]) {
                
                a[i].c+=a[j].c * w[i][j];
            }

        }
        if(!ans) a[i].c -=a[i].u ;//坑点啊，所以记得加特判
        if(a[i].c <=0) vis[a[i].c ]=1;//还是坑点，意思是，如果这个节点已经没法走了，那么它接下来的节点自然也无法利用它的c值，所以我们这里的vis判断这个节点的c值是否还可以用 
    }

    /*for(int i=1; i<=n; i++) cout<<a[i].c <<" ";
    cout<<endl;
*/


    memset(vis,1,sizeof(vis));

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
            if((a[i].c <=0&&w[i][j])||vis[i]==0) { //如果c值<=0
                ru[j]--;//又是坑点！如果当前的节点无法访问那么如果我们只用VIS来标记它的下一个节点也无法访问，那么会出现这样一种情况：如果这个节点有两条出路，那么没了一条它还可以走另一条啊！所以只用vis判断
//是不准确的，我们应该用更加准确的变量来表示关键点
                vis[i]=1;
            }
        }

    bool p=0;
    for(int i=1; i<=n; i++) {
        if(chu[i]==0&&ru[i]!=0&&a[i].c >0/*没错就是这里，这里还有一个坑点：可能在前面所有的节点中c都满足条件，但是你会发现在最后一个节点中c的值忽然变成负的了？！很操蛋是不是....如果变成了负的，也就是说明
这个c不可以被输出*/) {
            p=1;
            cout<<i<<" "<<a[i].c <<endl;
        }
    }

    if(!p) cout<<"NULL"<<endl;
    return 0;

}
/*
4 3
1 0
0 1
0 1
0 1
1 2 2
2 3 2
3 4 2
*/

/*
1.没有特判最后的c可能<=0的情况
2.一开始的找c值写挂了
3.也不知道为什么好好的常量a[3].c在程序运行过程中为啥会变值 
(没有判断输入源的值不可更改，必须为1)
*/

总结：
1.敲完题之后一定一定一定一定一定要！造数据！！！！在平时练习中就要养成这个习惯！！！！！必须！！！！！！

2.认真读题，等你把题敲完之后再去回看一遍题目（然后你会发现你漏掉了许多题目限制）(*^▽^*)‘’

3.思考缜密一点，（当然这可能要在长期的做题刷题中锻炼了扶额），尽量思考得全面一点，在你动手敲代码之前多造几组数据找找感觉，多造几种特殊数据看一看（比如图论里面的特殊数据就是链啊，树啊，有环图啊等等）

但是总的来说还是很开心的（虽然第一次提交只得了20分，虽然浪费了三个测试点之后还是只有60分）

但毕竟！！！这是你凭自己的力量做出来的啊！！！！

加油ヾ(◍°∇°◍)ﾉﾞ！！！！

----------------end----------------

码农公寓

题目背景

题目描述

输入格式

输出格式

输入输出样例

相关文章