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

# 例题

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```

## 代码

```#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]);
}
}
if (cnt == n) { //检查有环情况
ll ans = 888 * n;
for (int i = 1; i <= n; i++)
printf("%lld\n", ans);
}
else puts("-1");
}
return 0;
}```

# 小结

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

0 条评论

• ### 双向广搜-HDU1401 Solitaire

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

• ### 贪心-HDU1789 Doing Homework again(活动安排问题)

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

• ### 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...

• ### POJ-2585-Window Pains

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

• ### LeetCode Weekly Contest 41解题思路

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

• ### hdu---(1800)Flying to the Mars(trie树)

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

• ### poj-1012-约瑟夫问题

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