本文主要是介绍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;
}题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2647
这篇关于HDOJ 2647 Reward 【逆拓扑排序+分层】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
