2315235_wa.cpp

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

#include <stdio.h>
#include <algorithm>
#define MaxN 100001
#define MaxM 1000001
using namespace std;

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

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

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

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

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