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是一种比较一般化的套路...？ 因为拓扑保证了更新顺序 /* *********************************************** Author :111qqz …

http://poj.org/problem?id=3687 题意：给定几个标签球的重量大小关系，求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。 （输出是每个球第几重，而不是几号球比几号球重！）。一开始理解错了QAQ 思路：反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多？ /* *********************************************** Author :111qqz Created Time :2015年12月19日 星期六 16时32分59秒 File Name :code/poj/3687.cpp …

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，这样。。。只要不矛 …

http://acm.hdu.edu.cn/showproblem.php?pid=3342 裸题。 注意有重边。 /* *********************************************** Author :111qqz Created Time :2015年12月17日 星期四 19时29分00秒 File Name :code/hdoj/3342.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

http://codeforces.com/contest/510/problem/C 题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。 思路：将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串，从前往后扫，直到不相等的那一位，设为k,然后连边，指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串，那么不影响。如果后者是前者的字串，则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序（标准的）最小的方案。所以存点的时候用优先队列存。 /* …

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

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 …