洛谷1038 神经网络

原题链接

感觉这题在考我语文。。被坑了好几次。
说几个坑点：

1. 这个公式对输入层是无效的，也就是输入层是不需要减去\(U\)的。
2. 只有\(C > 0\)的时候才会往下传导。
3. 输出只要输出输出层且\(C > 0\)的点。

然后这个题其实就是一个简单的拓扑排序，每次给这个点所指向的点加上\(C * W\)，而在队列中取出点时再减去\(U\)即可。对于输入层，在扔入队列时给它的\(C\)加上\(U\)就可以了。

#include<cstdio>
using namespace std;
const int N = 110;
const int M = 1e4 + 10;
int di[M], da[M], ne[M], fi[N], q[M], C[N], U[N], ru[N], l, n;
bool v[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void add(int x, int y, int z) { di[++l] = y; da[l] = z; ne[l] = fi[x]; fi[x] = l; ru[y]++; v[x] = 1; }
void topsort()
{
    int i, x, y, head = 0, tail = 0;
    for (i = 1; i <= n; i++)
        if (!ru[i])
            q[++tail] = i, C[i] += U[i];
    while (head ^ tail)
    {
        x = q[++head];
        C[x] -= U[x];
        for (i = fi[x]; i; i = ne[i])
        {
            y = di[i];
            if (C[x] > 0)
                C[y] += da[i] * C[x];
            if (!(--ru[y]))
                q[++tail] = y;
        }
    }
}
int main()
{
    int i, m, x, y, z;
    bool p = 0;
    n = re(); m = re();
    for (i = 1; i <= n; i++)
        C[i] = re(), U[i] = re();
    for (i = 1; i <= m; i++)
    {
        x = re(); y = re(); z = re();
        add(x, y, z);
    }
    topsort();
    for (i = 1; i <= n; i++)
        if (!v[i] && C[i] > 0)
            printf("%d %d\n", i, C[i]), p = 1;
    if (!p)
        printf("NULL");
    return 0;
}

洛谷1038 神经网络

原文：https://www.cnblogs.com/Iowa-Battleship/p/10165491.html