拓扑排序

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

例题

传送门: HDU-2647web

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.spring

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.svg

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.spa

Sample Input:code

2 1
1 2
2 2
1 2
2 1

Sample Output:xml

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. 部分题的坑点：重复输入关系，须要特判一下。

你的点赞将会是我最大的动力