hdu 2647 rewards

2015年12月17日 0 作者 CrazyKK

http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:老板要给很多员工发奖金, 但是部分员工有个虚伪心态, 认为自己的奖金必须比某些人高才心理平衡; 但是老板很人道, 想满足所有人的要求, 并且很吝啬,想画的钱最少
输入若干个关系
a b
a c
c b
意味着a 的工资必须比b的工资高 同时a 的工资比c高; c的工资比b高

当出现环的时候输出-1

思路:因为点的个数比较多。。。用数组存点的关系存不下。。于是用set存边。。和用vector差不多。。。窝一开始的大思路错了。。以为会是一条链。。也就是没一个钱数只对应一个人。。。但实际上可以是889,888,888,这样。。。只要不矛盾。。然后要反向建图。。因为只知道最少的钱数是888,不知道最多的钱数是多少。。所以最先出来的,也就是入度为0的点应该为工资最少的。。。所以如果a应该比b工资高,那么连一条b指向a的边。