HDOJ 2647 Reward 【逆拓扑排序+分层】

题意：每一个人的基础工资是888。 因为一部分人要显示自己水平比較高，要求发的工资要比其它人中的一个人多。问你能不能满足他们的要求，假设能的话终于一共要发多少钱，假设不能就输出-1.

策略：拓扑排序。

这道题有些难点：一：数据大，建二维数组肯定不行，要换其它的数据结构（vector， 或者是链式前向星（本题代码用的是链式前向星））； 二：要逆拓扑排序（就是将++in[b]换成++in[a]）。 三要分层次（依据上一个的钱数+1就可以）。

不懂什么是链式前向星 移步：http://blog.csdn.net/acdreamers/article/details/16902023

代码：

#include<stdio.h>

#include<string.h>

#include<queue>

#define MAXN 10005

int head[MAXN*2];

struct EdgeNode{

	int to;

	int next;

};

EdgeNode edges[MAXN*2];

int in[MAXN], queue[MAXN], money[MAXN];

int n, ans;

int toposort()

{

	ans = 0;

	memset(money, 0, sizeof(money));

	int i, j;

	int iq = 0;

	for(i = 1; i <= n; i ++){

		if(!in[i]){

			queue[iq++] = i;

		}

	}

	for( i = 0; i < iq; i ++){

		int temp = queue[i];

		ans += money[temp];

		for(j = head[temp]; j != -1; j = edges[j].next){

			if(!--in[edges[j].to]){

				queue[iq++] = edges[j].to;

				money[edges[j].to] = money[temp]+1;//这里是分层次。

			}

		}

	}

	return iq == n;

}

int main()

{

	int m, i, a, b;

	while(scanf("%d%d", &n, &m) == 2){

		memset(head, -1, sizeof(head));

		memset(in, 0, sizeof(in));

		for(i = 0; i < m; i ++){

			scanf("%d%d", &a, &b);

				in[a]++;

				edges[i].to = a;

				edges[i].next = head[b];

				head[b] = i;

		}

		int sum = 888*n;

		int flag = toposort();

		printf("%d\n", flag?sum+ans:-1);

	}

	return 0;

}
 

题目链接：