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的边。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月09日 星期三 19时27分04秒
4File Name :code/hdu/2647.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=1E4+1;
34int n,m;
35set<int>conc[N];
36set<int>::iterator it;
37int in[N];
38int val[N];
39
40void topo()
41{
42 queue<int>q;
43 for ( int i = 1 ; i <= n ; i++)
44 if (in[i]==0) q.push(i);
45
46 int cnt = 0 ;
47 LL sum = 0 ;
48 while (!q.empty())
49 {
50 int v = q.front();
51 q.pop();
52 cnt++;
53
54 sum = sum + val[v];
55 for (it=conc[v].begin() ;it!=conc[v].end() ;it++)
56 {
57 if (val[*it]<val[v]+1)
58 {
59 val[*it] = val[v] + 1; //最根本的思路想错了。。。未必是个链啊。。可以一个2，两个1.。
60 //之前的算法默认成每一种钱数只能有一个人。。没有平级的。但实际上是可以有的。
61 }
62 in[*it]--;
63 if (in[*it]==0)
64 {
65 q.push(*it);
66 }
67 }
68 //conc[v].clear();
69 // for ( int i = 1 ; i <= n ; i++)
70// {
71// // if (!conc[v][i]) continue;
72// if (conc[v].count(i)==0) continue;
73// in[i]--;
74// if (in[i]==0) q.push(i);
75// }
76 }
77 if (cnt<n)
78 {
79 puts("-1");
80 }
81 else
82 {
83 printf("%lld\n",sum);
84 }
85}
86int main()
87{
88 #ifndef ONLINE_JUDGE
89 freopen("code/in.txt","r",stdin);
90 #endif
91
92 while (scanf("%d %d",&n,&m)!=EOF)
93 {
94 for ( int i = 0 ; i <= n ;i++) val[i] = 888;
95 for ( int i = 0 ; i <= n ; i++) conc[i].clear();
96 ms(in,0);
97 for ( int i = 0 ; i < m ; i++)
98 {
99 int x,y;
100 scanf("%d %d",&x,&y);
101 if (conc[y].count(x)==1) continue;
102 conc[y].insert(x);
103 in[x]++;
104 }
105 topo();
106 }
107
108 #ifndef ONLINE_JUDGE
109 fclose(stdin);
110 #endif
111 return 0;
112}