111qqz的小窝

老年咸鱼冲锋!

poj 3249 Test for Job (拓扑排序+dp)

http://poj.org/problem?id=3249

题意:

给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。

思路:

其实比较容易想到搜…不过复杂度会炸?

由于到一个点的最大点权和,需要更新完所有到达它的路线之后才能确定。

容易联想到拓扑排序,我们可以在拓扑排序的同时做dp

dp[v] = max(dp[v],dp[u]+a[v]),初始化对于入度为0的点,dp[i] = val[i].

其实拓扑+dp是一种比较一般化的套路…?

因为拓扑保证了更新顺序

 

poj 3687 Labeling Balls

http://poj.org/problem?id=3687
题意:给定几个标签球的重量大小关系,求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。
输出是每个球第几重,而不是几号球比几号球重!)。一开始理解错了QAQ
思路:反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多?

 

hdu 2647 rewards

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的边。

 

 

hdu 3342 Legal or Not

http://acm.hdu.edu.cn/showproblem.php?pid=3342
裸题。
注意有重边。

codeforces 510 C. Fox And Names

http://codeforces.com/contest/510/problem/C

题意:给定n个字符串。问是否存在一种字母顺序,使得这n个字符串的顺序满足字典序(自定义的)。如果有多种顺序,输出字典序(标准的)最小的。

思路:将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串,从前往后扫,直到不相等的那一位,设为k,然后连边,指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串,那么不影响。如果后者是前者的字串,则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序(标准的)最小的方案。所以存点的时候用优先队列存。

 

hdu 2094 产生冠军

题意:给定n组u关系。每组表示a战胜b。。问根据这些关系能否确定冠军。
思路:如果a战胜b就从a连一条指向b的边。那么能确定冠军的条件就变成了,有且只有一个入度为0的点。翻译过来就是,有一个人没有被任何人战胜过。且,这样的人只有一个。一开始想用map来搞。。但是比较麻烦。。其实用set比较好。。开两个set,一个存所有的人,一个存输过的人。出度为0的点只有一个等价为,有且只有一个人没有输过。也就是两个set的元素差个数为1.

hdoj 1285 确定比赛名次

http://acm.hdu.edu.cn/showproblem.php?pid=1285
题意:

有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
拓扑排序模板题。刷dfs的时候遇到的。干脆来学习下。
注意可能有重边。
由于要求输出顺序按照序号从小到达,所以这里用了优先队列。