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

/* ***********************************************
Author :111qqz
Created Time :2015年12月09日 星期三 19时27分04秒
File Name :code/hdu/2647.cpp
************************************************ */
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E4+1;
 7int n,m;
 8set<int>conc[N];
 9set<int>::iterator it;
10int in[N];
11int val[N];
1void topo()
2{
3    queue<int>q;
4    for ( int i = 1 ; i <= n ; i++)
5	if (in[i]==0) q.push(i);
1    int cnt = 0 ;
2    LL sum = 0 ;
3    while (!q.empty())
4    {
5	int v = q.front();
6	q.pop();
7	cnt++;
 1	sum = sum + val[v];
 2	for (it=conc[v].begin() ;it!=conc[v].end() ;it++)
 3	{
 4	    if (val[*it]<val[v]+1)
 5	    {
 6		val[*it] = val[v] + 1;  //最根本的思路想错了。。。未必是个链啊。。可以一个2,两个1.。
 7					//之前的算法默认成每一种钱数只能有一个人。。没有平级的。但实际上是可以有的。
 8	    }
 9	    in[*it]--;
10	    if (in[*it]==0)
11	    {
12		q.push(*it);
13	    }
14	}
15	//conc[v].clear();
16	//	for ( int i = 1 ; i <= n ; i++)
17//	{
18//	   // if (!conc[v][i]) continue;
19//	    if (conc[v].count(i)==0) continue;        
20//	    in[i]--;
21//	    if (in[i]==0) q.push(i);
22//	}
23    }
24    if (cnt<n)
25    {
26	puts("-1");
27    }
28    else
29    {
30	printf("%lld\n",sum);
31    }
32}
33int main()
34{
35	#ifndef  ONLINE_JUDGE 
36	freopen("code/in.txt","r",stdin);
37  #endif
 1	while (scanf("%d %d",&n,&m)!=EOF)
 2	{
 3	    for ( int i = 0 ; i <= n ;i++) val[i] = 888;
 4	    for ( int i =  0 ; i <= n ; i++) conc[i].clear();
 5	    ms(in,0);
 6	    for ( int i = 0 ; i < m ; i++)
 7	    {
 8		int x,y;
 9		scanf("%d %d",&x,&y);
10		if (conc[y].count(x)==1) continue;
11		conc[y].insert(x);
12		in[x]++;
13	    }
14	    topo();
15	}
1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}