神經網絡(NOip2003第1題)
Time Limit: 1 second Memory Limit: 50 MB
【問題背景】 人工神經網絡（Artificial Neural Network）是一種新興的具有自我學習能力的計算系統，在模式識別、函數逼近及貸款風險評估等諸多領域有廣泛的應用。對神經網絡的研究一直是當今的熱門方向，蘭蘭同學在自學了一本神經網絡的入門書籍后，提出了一個簡化模型，他希望你能幫助他用程序檢驗這個神經網絡模型的實用性。
【問題描述】 在蘭蘭的模型中，神經網絡就是一張有向圖，圖中的節點稱為神經元，而且兩個神經 元之間至多有一條邊相連，下圖是一個神經元的例子：
圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經元目前的狀態， Ui是閾值，可視為神經元的一個內在參數。 神經元按一定的順序排列，構成整個神經網絡。在蘭蘭的模型之中，神經網絡中的神 經無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經元只向下一層的神經元 輸出信息，只從上一層神經元接受信息。下圖是一個簡單的三層神經網絡的例子。蘭蘭規定，Ci服從公式：（其中n是網絡中所有神經元的數目）公式中的Wji（可能為負值）表示連接j號神經元和 i號神經元的邊的權值。當 Ci大于0時，該神經元處于興奮狀態，否則就處于平靜狀態。當神經元處于興奮狀態時，下一秒它會向其他神經元傳送信號，信號的強度為Ci。 如此．在輸入層神經元被激發之后，整個網絡系統就在信息傳輸的推動下進行運作。 現在，給定一個神經網絡，及當前輸入層神經元的狀態（Ci），要求你的程序運算出最后網 絡輸出層的狀態。【輸入】
共n+p+1行；第一行是兩個整數n（1≤n≤20）和p;接下來的N行,每行兩個整數，第i＋1行是神經元i最初狀態和其閾值（Ui），非輸入層的神經元開始時狀態必然為0。再下面P行，每行由兩個整數i，j及一個整數Wij，表示連接神經元i、j的邊權值為Wij。【輸出】
輸出包含若干行，每行有兩個整數，分別對應一個神經元的編號，及其最后的狀 態，兩個整數間以空格分隔。僅輸出最后狀態非零的輸出層神經元狀態，并且按照編號由小到大順序輸出！若輸出層的神經元最后狀態均為 0，則輸出 NULL。【輸入樣例】
5 61 01 00 10 10 11 3 11 4 11 5 12 3 12 4 12 5 1【輸出樣例】
3 14 15 1【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=b301
【題意】
【題解】 按照題目去模擬那個過程就好。 加上一個記憶化搜索。 題目最后輸出的是大于0的狀態,小于等于0的狀態都不要輸出哦。 N最大是200而不是20.。題目有誤。 【完整代碼】
#include <cstdio>#include <cstring>#include <vector>#include <iostream>using namespace std;#define rei(x) scanf("%d",&x)#define rep1(i,x,y) for (int i = x;i <= y;i++)const int N = 200 + 10;int n, p;int c[N],u[N],ru[N],f[N],chu[N];vector <int> G[N],W[N];bool bo[N];int dfs(int x){ if (bo[x]) { if (f[x] > 0) return f[x]; else return 0; } int len = G[x].size(); int sum = 0; rep1(i, 0, len - 1) { int y = G[x][i], w = W[x][i]; sum += dfs(y)*w; } f[x] = sum - u[x]; bo[x] = true; if (f[x] > 0) return f[x]; else return 0;}int main(){ //freopen("D://rush.txt", "r", stdin); //freopen("D://rush_out.txt", "w", stdout); memset(f, 255, sizeof f); rei(n), rei(p); rep1(i, 1, n) { rei(c[i]), rei(u[i]); } rep1(i, 1, p) { int x, y, z; rei(x), rei(y), rei(z); G[y].push_back(x); W[y].push_back(z); ru[y]++,chu[x]++; } rep1(i, 1, n) if (ru[i] == 0) f[i] = c[i], bo[i] = true; rep1(i, 1, n) if (!bo[i]) dfs(i); int cnt = 0; rep1(i, 1, n) if (chu[i] == 0) { if (f[i] > 0) {新聞熱點
疑難解答
