Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4746 Accepted Submission(s): 1448
Problem Description 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个需求 (a,b)，表示a的奖金要比b的多，然后呢，老板决定每个员工至少可以拿888元，现在老板总共至少需要发多少奖金。
如果满足不了就输出-1。
分析：拓扑排序问题。比第i个人奖金少的总人数有sum个，那么第i个人的奖金就是888+sum元。注意此题数据比较大，用邻接表存吧。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2647
代码清单：
(1) vector实现
?
#include
|