洛谷 P1038 神经网络

https://www.luogu.org/problemnew/show/P1038

JDOJ 1278: [NOIP2003]神经网络 T1

https://neooj.com:8082/oldoj/problem.php?id=1278

题目请自点链接，太麻烦了。

思路解析：

一开始看这道题不是很难，想了想就去做，后来发现这题的坑点细节比较多，需要一一讲解处理。

正解-拓扑排序。

为什么要用拓扑排序呢？

不知道大家怎么想，在做这道题之前，在我印象中用拓扑排序的题大概都长这样：

A打败了B，B打败了D...等类似模型。

所以我并没有深入地理解拓扑排序。

所谓的拓扑排序，其实就是有向图拓展的一种序列。

我们这道题给出了一个求和公式（说到求和公式，这需要数学知识，我一开始也看不懂，后来查了百科看了题解才勉强整明白...）

说明每一个顶点的C值需要从上一个节点处递推。

再结合这道题有向图的本体。

自然而然地想出求拓扑序。

拓扑排序的模板请大家自行参照水题学习，这道题需要有一点点变化（绝对不多！！

AC 代码如下：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
queue<int> q;
int n,p,cnt;
int chudu[110],v[110],c[110];
int tot,to[11000],val[11000],nxt[11000],head[110],from[11000];
struct answer
{
    int id,val;
}ans[110];
void add(int x,int y,int z)
{
    to[++tot]=y;
    val[tot]=z;
    nxt[tot]=head[x];
    from[tot]=x;
    head[x]=tot;
}
bool cmp(answer a,answer b)
{
    return a.id<b.id;
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
    {
        int u;
        chudu[i]=0;
        scanf("%d%d",&c[i],&u);
        if(c[i])
        {
            q.push(i);
            v[i]=1;
        }
        else
            c[i]-=u;
    }
    for(int i=1;i<=p;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        chudu[x]=1;
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            if(c[from[i]]<=0)
                continue;
            int y=to[i];
            c[y]+=(val[i]*c[x]);
            if(v[y]==0)
            {
                q.push(y);
                v[y]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(c[i]>0 && chudu[i]==0)
        {
            ans[++cnt].id=i;
            ans[cnt].val=c[i];
        }
    if(cnt==0)
    {
        printf("NULL");
        return 0;
    }
    sort(ans+1,ans+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        printf("%d %d\n",ans[i].id,ans[i].val);
    return 0;
}

我jio得大家应该能看懂。