拓扑排序-HDU2647 Reward

文章目录

• 拓扑排序
• 例题
• • 题意
  • 分析
  • 代码
• 小结

拓扑排序

什么是拓扑排序？ 简单来说，在做一件事之前必须先做另一(几)件事都可抽象为图论中的拓扑排序，比如课程学习的先后，安排客人座位等。 一个图能拓扑排序的充要条件是它是有向无环图。将问题转为图，比如A指向B代表完成B前要先完成A，那么用数组记录入度，从入度为0的开始搜索(bfs/dfs)和维护数组，即可得到拓扑排序。

例题

传送门: HDU-2647

Dandelion’s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards. The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a’s reward should more than b’s.Dandelion’s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work’s reward will be at least 888 , because it’s a lucky number.

Input:

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000) then m lines ,each line contains two integers a and b ,stands for a’s reward should be more than b’s.

Output:

For every case ,print the least money dandelion ‘s uncle needs to distribute .If it’s impossible to fulfill all the works’ demands ,print -1.

Sample Input:

2 1
1 2
2 2
1 2
2 1

Sample Output:

1777
-1

题意

每组输入两个数n（人数）,m（关系数）。接下来的m行输入a，b表示a的奖金大于b，其中每个人奖金至少为888，求老板至少发多少钱，若不能合理分配则输出-1。

分析

用need[]存入度数，再用数组add[]表示某人在888的基础上多发的钱。先将入度为0的入队，然后bfs并维护数组，因为求至少发的钱，那么a比b多1即可。最后用cnt判断求出来点数是否等于总数，排除有环情况。

代码

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 20004;
int n, m, x, y;
int main() {
	while (~scanf("%d%d", &n, &m)) {
		vector<int>v[maxn];
		int need[maxn] = { 0 };//入度
		int add[maxn] = { 0 };//某人至少多发多少钱才满足要求
		while (m--) {
			scanf("%d%d", &x, &y);
			v[y].push_back(x);//x比y多(y指向x):即求x前要先求y
			need[x]++;
		}
		queue<int>q;
		for (int i = 1; i <= n; i++)
			if (need[i] == 0)
				q.push(i);//入度为0的先入队
		int cnt = 0;
		while (q.empty() == false) {
			int cur = q.front();
			q.pop();
			cnt++;
			for (int i = 0; i < v[cur].size(); i++)
				if (--need[v[cur][i]] == 0) {
					q.push(v[cur][i]);
					add[v[cur][i]] = max(add[v[cur][i]], add[cur] + 1);
				}
		}
		if (cnt == n) { //检查有环情况
			ll ans = 888 * n;
			for (int i = 1; i <= n; i++)
				ans += add[i];
			printf("%lld\n", ans);
		}
		else puts("-1");
	}
	return 0;
}

小结

1. 符合条件的拓扑排序可能有多种，按题目要求（如字典序等）使用优先队列来实现即可。
2. 用反向建图解决某些奇奇怪怪?的排序要求
3. 部分题的坑点：重复输入关系，需要特判一下。

原创不易，请勿转载（本不富裕的访问量雪上加霜 ） 博主首页：https://blog.csdn.net/qq_45034708