2315122_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 62 行

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MaxN 100001
#define MaxM 1000001
#define max(a,b) a>b?a:b
using namespace std;

__int64 MAX, ans[MaxN];
long n, m;
long v[MaxN];
long d[MaxN], D[MaxN];
struct node
{
	long st, ed;
}way[MaxM];

bool cmp(struct node a,struct node b)
{
	return d[a.st]<d[b.st];
}

int input()
{
	long i;
	long st, ed;

	if(scanf("%ld%ld",&n,&m)!=2)
		return 0;
	memset(ans,0,sizeof(ans));
	memset(D,0,sizeof(D));
	memset(d,0,sizeof(d));
	for(i = 0; i < n; i++)
		scanf("%ld",&v[i]);
	for(i = 0; i < m; i++)
	{
		scanf("%ld%ld",&st,&ed);
		way[i].st = st-1;way[i].ed = ed-1;
		d[ed-1]++;D[st-1]++;
	}
	sort(way,way+n,cmp);
	for(i = 0; i < m; i++)
	{
		st = way[i].st;ed = way[i].ed;
		if(d[st]==0)
			ans[st] = v[st];
		ans[ed] = max(ans[ed],ans[st]+v[ed]);
	}
	MAX = -1000000000;
	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;
}