[Leaf] P1038 神经网络

p1038-[noip-2003-提高组]-神经网络---洛谷">P1038 [NOIP 2003 提高组] 神经网络 - 洛谷

1. 题面梗概

中译中: 这是一个 DAG 上的信号传递模拟。每个节点接收前驱节点的加权信号。

当信号总量减去自身阈值 $U_i$ 后仍大于 $0$，该节点被激活，并将信号继续传递给后继节点。我们需要输出所有处于激活状态的输出层节点。

2. 逻辑推导

发现节点之间存在很明显的前驱后继关系，直觉上就是按层遍历，在图论中也就是拓扑排序。

2.1 拓扑排序

我们从这个公式入手：

$$C_i = \left( \sum_{(j,i) \in E}W_{j,i}\cdot C_j \right) - u_i$$

我们发现，每个节点的 $C$ 实际上就是 入流量总和 和 启动成本 的差值。

而如果某个点 $C_i \leq 0$，那么它就不会启动，自然不会影响到后面的点。

因此，我们可以按照拓扑排序的顺序，按层模拟，同时就把前面有效的节点权值向后传递。

2.2 结论

很标准的一道拓扑排序。

3. 代码实现

▶

AcCode

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

const int maxn = 100 + 5;

struct Edge { int v, w; };
vector<Edge> adj[maxn];

int indeg[maxn], outdeg[maxn];
bool is_input[maxn];
int c[maxn], u[maxn];
int n, p;

void solve( )
{
    cin >> n >> p;
    for( int i = 1; i <= n; ++ i )
    {
        cin >> c[i] >> u[i];
        if( c[i] > 0 ) is_input[i] = 1;
    }

    for( int i = 1; i <= p; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back( {v, w} );
        indeg[v] ++;
        outdeg[u] ++;
    }

    queue< int > q;
    for( int i = 1; i <= n; ++ i )
    {
        if( indeg[i] == 0 ) q.push( i );
        else c[i] -= u[i];
    }

    while( !q.empty( ) )
    {
        int u = q.front( );
        q.pop( );

        if( c[u] > 0 )
        {
            for( auto [v, w] : adj[u] )
            {
                c[v] += c[u] * w;
            }
        }

        for( auto [v, w] : adj[u] )
        {
            indeg[v] --;
            if( indeg[v] == 0 ) q.push( v );
        }
    }


    bool exist = 0;
    vector< pair< int, int > > res;
    for( int i = 1; i <= n; ++ i )
    {
        if( outdeg[i] == 0 && c[i] > 0 )
        {
            res.push_back({ i, c[i] });
            exist = 1;
        }
    }

    if( !exist )
    {
        cout << "NULL" << '\n';
        return ;
    }
    sort( res.begin( ), res.end( ) );
    for( auto [i, j] : res )
    {
        cout << i << ' ' << j << '\n';
    }
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O(N + P)$。

• 碎碎念：拓扑排序是不难，但是这个建模比较麻烦。

• 关联知识点： 拓扑排序