记录编号	313202	评测结果	AAAAAAA
题目名称	[NOIP 2003]神经网络	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-09-28 18:55:01	内存使用	10.12 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=2000;
int n,p;int tot=0;
int c[maxn];
int u[maxn];
int count[maxn];
bool print[maxn];
bool inque[maxn]={0};
queue<int> q;
struct edges
{
  int f;int t;int w;
} edge[1000000];
vector<int> G[maxn];

void bfs()
{   
   while(!q.empty())
       
  {   int x=q.front(); q.pop(); inque[x]=0;
     if(!c[x])
	c[x]=count[x]-u[x];
	//printf("%d %d\n",x,c[x]);
    if(c[x]>0)
    for(int i=0;i<G[x].size();i++)
    { 
	  edges &e=edge[G[x][i]];
	  count[e.t]+=e.w*c[x];
	  if(!inque[e.t])
	  {
	   q.push(e.t); inque[e.t]=1;
      }
    }
  }
}
int main()
{ 

  freopen("sjwl.in","r",stdin);
  freopen("sjwl.out","w",stdout);
  memset(count,0,sizeof(count));
  memset(c,0,sizeof(c));
  scanf("%d%d",&n,&p);
  for(int i=1;i<=n;i++)
   print[i]=1;
  for(int i=1;i<=n;i++)
   scanf("%d%d",&c[i],&u[i]);
  for(int i=1;i<=p;i++)
    {
	   int a,b,w;
	   scanf("%d%d%d",&a,&b,&w);
	   tot++;
	   edge[tot].f=a; edge[tot].t=b; edge[tot].w=w;
	   G[a].push_back(tot);
	   print[a]=0;
	}
  for(int i=1;i<=n;i++)
    if(c[i]!=0)
	  {
	    edges a;
		a.f=0;a.t=i; a.w=0;
		edge[++tot]=a;
		G[0].push_back(tot);
	  }
   c[0]=1;u[0]=0;
   q.push(0);
   bfs();
   bool flag=0;
   for(int i=1;i<=n;i++)
     {
	   if(print[i]&&c[i]>0)
	   printf("%d %d\n",i,c[i]),flag=1;
	 }
	if(!flag)
	printf("NULL");
   return 0;
}