拓扑排序-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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 双向广搜-HDU1401 Solitaire

    什么是双向广搜? 如果把bfs想象成在平静的池塘丢一颗石头,激起的波浪一层层扩散到整个空间直到到达目标,就得到起点到终点的最优路径。那么双向广搜就是在起点和终...

    唔仄lo咚锵
  • 贪心-HDU1789 Doing Homework again(活动安排问题)

    首先把作业按截止日期从小到大排序,如果日期相同按罚分降序,我们希望完成尽可能多的作业。然而仅靠日期排序并不是最优的,当一项作业超过截止日期时,我们不能就简单的加...

    唔仄lo咚锵
  • 动态规划-区间DP

    唔仄lo咚锵
  • 图论--差分约束--POJ 3159 Candies

    风骨散人Chiam
  • Codeforce-Ozon Tech Challenge 2020-D. Kuroni and the Celebration(交互题+DFS)

    After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Ku...

    风骨散人Chiam
  • POJ-2585-Window Pains

    Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

    某些人
  • LeetCode Weekly Contest 41解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • hdu---(1800)Flying to the Mars(trie树)

    Flying to the Mars Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768...

    Gxjun
  • 实验2 C++数组与指针

    步行者08
  • poj-1012-约瑟夫问题

    The Joseph's problem is notoriously known. For those who are not familiar with t...

    瑾诺学长

扫码关注云+社区

领取腾讯云代金券