拓扑排序

http://poj.org/problem?id=3249 题意： # 给一个DAG,现要从一条入度为0的点到一个出度为0的点，问最大点权和。

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

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

http://acm.hdu.edu.cn/showproblem.php?pid=3342 裸题。 注意有重边。 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月17日 星期四 19时29分00秒 4File Name :code/hdoj/3342.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E2+7; 34 35int n,m; 36 37bool v[N][N]; 38int in[N]; 39 40void topo() 41{ 42 queue<int>q; 43 44 for ( int i = 0 ; i < n ; i++) 45 { 46 if (in[i]==0) q.push(i); 47 } 48 49 int cnt = 0 ; 50 while (!q.empty()) 51 { 52 cnt++; 53 int u = q.front(); q.pop(); 54 55 for ( int i = 0 ; i< n ; i++) 56 { 57 if (!v[u][i]) continue; 58 59 in[i]--; 60 if (in[i]==0) 61 { 62 q.push(i); 63 } 64 } 65 } 66 if (cnt==n) 67 { 68 puts("YES"); 69 } 70 else 71 { 72 puts("NO"); 73 } 74} 75int main() 76{ 77 #ifndef ONLINE_JUDGE 78 freopen("code/in.txt","r",stdin); 79 #endif 80 81 while (~scanf("%d %d",&n,&m)!=EOF) 82 { 83 if (n==0) break; 84 ms(v,false); 85 ms(in,0); 86 while (m--) 87 { 88 int x,y; 89 scanf("%d %d",&x,&y); 90 if (v[x][y]) continue ; //重边? 91 v[x][y] = true; 92 in[y]++; 93 } 94 95 topo(); 96 } 97 98 #ifndef ONLINE_JUDGE 99 fclose(stdin); 100 #endif 101 return 0; 102}

http://codeforces.com/contest/510/problem/C 题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。

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

http://acm.hdu.edu.cn/showproblem.php?pid=1285 题意： 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。