题解 | #神经网络#

//拓扑排序的方式来计算出下一个点的状态，然后一次类推到下下个点。一直到最后。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 202;
//使用链式前向星去存储图
struct sy{
    int to;
    int next;
    int w;
}edge[20002];
struct Node{
    int u;
    int c;
} node[maxn];
int head[maxn];
int in[maxn], to[maxn], to_cnt=0;
vector<pair<int, int> > pr;
int cnt = 0;
int n, p;
//链式前向星加边
void add_edge(int x, int y, int w)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    head[x] = cnt;
}

bool comp(pair<int, int> p1, pair<int, int> p2)
{
    return p1.first<p2.first;
}

void topu()
{
    queue<int> q;
    //走一遍所有的节点，将入度为0的节点加入进队列里面。
    for (int i=1;i<=n;i++)
    {
//         cout<<"i="<<i<<" in[i]="<<in[i]<<endl;
        if (in[i]==0)
        {
            q.push(i);
//             cout<<"i="<<i<<endl;
        }
    }
    while (q.size())
    {
        bool flag = false;
        int pos = q.front();
//         cout<<"pos="<<pos<<endl;
        q.pop();
        if (node[pos].c<=0) continue;
        for (int i=head[pos];i!=-1;i = edge[i].next)
        {
            int next = edge[i].to;
            int w = edge[i].w;
            int c = node[pos].c;
            node[next].c += w*c;
            in[next]--;
            if (in[next]==0)
            {
                q.push(next);
            }
            flag = true;
        }
        if (flag) node[pos].c = 0;
    }
}

signed main()
{
    memset(head, -1, sizeof(head));
    int x, y, w;
    cin>>n>>p;
    for (int i=1;i<=n;i++)
    {
        cin>>node[i].c;
        cin>>node[i].u;
        if (node[i].c==0)
        {
            node[i].c -= node[i].u;
        }
    }
    for (int i=1;i<=p;i++)
    {
        cin>>x>>y>>w;
        in[y]++;
        add_edge(x, y, w);
    }
    topu();
    for (int i=1;i<=n;i++)
    {
        if (node[i].c>0)
        {
            pr.push_back({i, node[i].c});
        }
    }
    sort(pr.begin(), pr.end(), comp);
    if (pr.size()==0)
    {
        cout<<"NULL"<<endl;
        return 0;
    }
    vector<pair<int, int> >::iterator it;
    for (it=pr.begin();it!=pr.end();it++)
    {
        cout<<(*it).first<<" "<<(*it).second<<endl;
    }
    return 0;
}