拓扑排序

题目链接

题解

读完题目后，发现出每个中间层的点都是由上一层的点的状态算出来的，于是可以轻松想到是拓扑排序。

注意，这个题目有以下坑点：

1. 根据题目可知，当一个神经元的兴奋值为负数，它就不可能向下传递了。这里要特判，因为这个调了好久。
2. 输出时编号从小到大。
3. $u_i$在每次计算时只需要减一次。

如果碰到出度为0并且状态是兴奋的点，就计入答案，最后排序。

提示：

1. 出度不需要单独计算，用邻接表的head[]数组便可。
2. 非输入层的神经元开始时状态必然为$0$ (来自题目)。

---

代码

代码应该很好懂，不写太多注释了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
const int maxn = 105;
struct node
{
    int to, next, data;
} edge[maxn * maxn << 1];
 
int head[maxn], num, n, p, rd[maxn], c[maxn], U[maxn];
vector<pair<int, int>> ans;
queue<int> q;
 
inline void add(int from, int to, int data)
{
    edge[++num] = (node){to, head[from], data};
    head[from] = num;
    rd[to]++; //计算入度
}
 
void toposort()
{
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
 
        c[u] -= U[u];
        if (head[u] == 0)
            if (c[u] > 0)
                ans.push_back(make_pair(u, c[u]));
 
        for (int i = head[u]; i; i = edge[i].next)
        {
            int to = edge[i].to;
            if (c[u] > 0) //如果它不是兴奋的就不能更新
                c[to] += edge[i].data * c[u];
            rd[to]--;
            if (rd[to] == 0)
                q.push(to);
        }
    }
    if (ans.size() == 0)
    {
        cout << "NULL" << endl;
        return;
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < (int)ans.size(); i++)
        cout << ans[i].first << " " << ans[i].second << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> p;
    for (register int i = 1; i <= n; i++)
    {
        cin >> c[i] >> U[i];
        if (c[i] != 0)
        {
            U[i] = 0;
            q.push(i);
        }
    }
 
    for (register int i = 1, x, y, w; i <= p; i++)
    {
        cin >> x >> y >> w;
        add(x, y, w);
    }
    toposort();
    return 0;
}

$$finish$$