2314674_ce.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT (EdgeNode *)malloc(sizeof(EdgeNode))

__int64 Max, ans[100001];
long d[100001], D[100001];
long queue[100001];
long f, r, n, m;
typedef struct node
{
	long adj;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	int w;
	EdgeNode *head;
}VertexNode;
typedef VertexNode AdjList[100001];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;
Graphic G;

__int64 max(__int64 a,__int64 b)
{
	return a>b?a:b;
}
int input()
{
	long i, tmp, tmp1;
	long st, ed;
	EdgeNode *s;

	if(scanf("%ld%ld",&n,&m)!=2)
		return 0;
	memset(d,0,sizeof(d));
	memset(D,0,sizeof(D));
	memset(ans,0,sizeof(ans));
	for(i = 0; i < n; i++)
	{
		G.adjlist[i].head = INIT;
		G.adjlist[i].head->next = NULL;
		scanf("%d",&G.adjlist[i].w);
	}
	for(i = 0; i < m; i++)
	{
		scanf("%ld%ld",&st,&ed);
		s = INIT;
		s->adj = ed-1;
		s->next = G.adjlist[st-1].head->next;
		G.adjlist[st-1].head->next = s;
		d[ed-1]++;D[st-1]++;
	}
	f = r = -1;
	for(i = 0; i < m; i++)
	{
		if(d[i]==0)
		{
			queue[++f] = i;
			ans[i] = G.adjlist[i].w;
		}
	}
	while(f!=r)
	{
		++r;
		tmp = queue[r];
		s = G.adjlist[tmp].head;
		while(s->next)
		{
			tmp1 = s->next->adj;
			ans[tmp1] = max(ans[tmp1],G.adjlist[tmp1].w+ans[tmp]);
			d[tmp1]--;
			if(d[tmp1]==0)
				queue[++f] = tmp1;
			s = s->next;
		}
	}
	Max = -1;
	for(i = 0; i < n; i++)
		if(D[i]==0&&ans[i]>Max)
			Max = ans[i];
	printf("%I64d\n",Max);
	return 1;
}

int main()
{
	while(input());
	return 1;
}