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}

相关文章