3217879_ac_875ms_2176k.cpp

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

#include <stdio.h>
#include <vector>
#include <algorithm>
#define maxv 50001

using namespace std;

int n, m;

struct node
{
	int p, d;
};

node job[maxv];
int din[maxv];
vector <int> map[maxv];
int heap[maxv], r;

bool cmp(int a,int b)
{
	if(job[a].d==job[b].d)
		return job[a].p > job[b].p;
	else
		return job[a].d > job[b].d;
}

int main()
{
	int i, a, b, t;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&job[i].p,&job[i].d);
	}
	scanf("%d",&m);
	fill_n(din,n,0);
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&a,&b);
		map[a-1].push_back(b-1);
		din[b-1]++;
	}
	r = 0;
	for(i = 0; i < n; i++)
	{
		if(din[i]==0)
		{
			heap[r++] = i;
			push_heap(heap,heap+r,cmp);
		}
	}
	while(r > 0)
	{
		t = heap[0];
		printf("%d\n",t+1);
		pop_heap(heap,heap+r,cmp);
		r--;
		for(i = 0; i < map[t].size(); i++)
		{
			din[map[t][i]]--;
			if(din[map[t][i]]==0)
			{
				heap[r++] = map[t][i];
				push_heap(heap,heap+r,cmp);
			}
		}
	}
	return 0;
}