记录编号	15436	评测结果	AAAAAAW
题目名称	[NOIP 2003]神经网络	最终得分	85
用户昵称	yanzheng	是否通过	未通过
代码语言	C	运行时间	0.008 s
提交时间	2009-11-12 22:28:25	内存使用	7.91 MiB

#include <stdio.h>

long n,p;
long c[1002]={},u[1002]={},in[1002]={},f[1002]={},top=0;
long w[1002][1002]={},a[1002][1002]={};

void px()
{
    long p=1,i,j;

    while(p)
    {
        p=0;top++;

        for(i=1;i<=n;i++)
        {
            if(!in[i] && !f[i])
            {
                p=1;f[i]=top;
            }
        }

        for(i=1;i<=n;i++)
        {
            if(f[i]==top)
            {
                for(j=1;j<=n;j++)
                {
                    if(a[i][j] && !f[j])
                        in[j]--;
                }
            }
        }
    }

    top--;
}

void doit()
{
    long i,j,k;

    for(i=2;i<=top;i++)
    {
        for(k=1;k<=n;k++)
        {
            if(f[k]==i)
            {
                c[k]=-u[k];
                for(j=1;j<=n;j++)
                    if(a[j][k] && c[j]>0)
                        c[k]+=w[j][k]*c[j];
            }
        }
    }
}

void print()
{
    freopen("sjwl.out","w",stdout);
    long k=0,i;

    for(i=1;i<=n;i++)
    {
        if(f[i]==top && c[i]>0)
        {
            printf("%ld %ld\n",i,c[i]);
            k++;
        }
    }

    if(!k)
        printf("NULL\n");
}

int main()
{
    freopen("sjwl.in","r",stdin);

    long i,j,k,t;

    scanf("%d %d",&n,&p);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&c[i],&u[i]);
    }

    for(k=0;k<p;k++)
    {
        scanf("%d %d %d",&i,&j,&t);
        w[i][j]=t;a[i][j]=1;
        in[j]++;
    }

    px();

    doit();

    print();

    return 0;
}