hdu 2647 rewards

2015年12月17日 0 作者 CrazyKK

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
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+1;
int n,m;
set<int>conc[N];
set<int>::iterator it;
int in[N];
int val[N];

void topo()
{
    queue<int>q;
    for ( int i = 1 ; i <= n ; i++)
	if (in[i]==0) q.push(i);

    int cnt = 0 ;
    LL sum = 0 ;
    while (!q.empty())
    {
	int v = q.front();
	q.pop();
	cnt++;
	
	sum = sum + val[v];
	for (it=conc[v].begin() ;it!=conc[v].end() ;it++)
	{
	    if (val[*it]<val[v]+1)
	    {
		val[*it] = val[v] + 1;  //最根本的思路想错了。。。未必是个链啊。。可以一个2，两个1.。
					//之前的算法默认成每一种钱数只能有一个人。。没有平级的。但实际上是可以有的。
	    }
	    in[*it]--;
	    if (in[*it]==0)
	    {
		q.push(*it);
	    }
	}
	//conc[v].clear();
	//	for ( int i = 1 ; i <= n ; i++)
//	{
//	   // if (!conc[v][i]) continue;
//	    if (conc[v].count(i)==0) continue;        
//	    in[i]--;
//	    if (in[i]==0) q.push(i);
//	}
    }
    if (cnt<n)
    {
	puts("-1");
    }
    else
    {
	printf("%lld\n",sum);
    }
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	while (scanf("%d %d",&n,&m)!=EOF)
	{
	    for ( int i = 0 ; i <= n ;i++) val[i] = 888;
	    for ( int i =  0 ; i <= n ; i++) conc[i].clear();
	    ms(in,0);
	    for ( int i = 0 ; i < m ; i++)
	    {
		int x,y;
		scanf("%d %d",&x,&y);
		if (conc[y].count(x)==1) continue;
		conc[y].insert(x);
		in[x]++;
	    }
	    topo();
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

/* ***********************************************

Author :111qqz

Created Time :2015年12月09日星期三 19时27分04秒

File Name :code/hdu/2647.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

#define pi pair < int ,int >

#define MP make_pair

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

const int N=1E4+1;

int n,m;

set<int>conc[N];

set<int>::iterator it;

int in[N];

int val[N];

void topo()

{

queue<int>q;

for ( int i = 1 ; i <= n ; i++)

if (in[i]==0) q.push(i);

int cnt = 0 ;

LL sum = 0 ;

while (!q.empty())

{

int v = q.front();

q.pop();

cnt++;

sum = sum + val[v];

for (it=conc[v].begin() ;it!=conc[v].end() ;it++)

{

if (val[*it]<val[v]+1)

{

val[*it] = val[v] + 1; //最根本的思路想错了。。。未必是个链啊。。可以一个2，两个1.。

//之前的算法默认成每一种钱数只能有一个人。。没有平级的。但实际上是可以有的。

}

in[*it]--;

if (in[*it]==0)

{

q.push(*it);

}

//conc[v].clear();

// for ( int i = 1 ; i <= n ; i++)

// {

// // if (!conc[v][i]) continue;

// if (conc[v].count(i)==0) continue;

// in[i]--;

// if (in[i]==0) q.push(i);

// }

}

if (cnt<n)

{

puts("-1");

}

else

{

printf("%lld\n",sum);

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

while (scanf("%d %d",&n,&m)!=EOF)

{

for ( int i = 0 ; i <= n ;i++) val[i] = 888;

for ( int i = 0 ; i <= n ; i++) conc[i].clear();

ms(in,0);

for ( int i = 0 ; i < m ; i++)

{

int x,y;

scanf("%d %d",&x,&y);

if (conc[y].count(x)==1) continue;

conc[y].insert(x);

in[x]++;

}

topo();

}

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

分类目录hdoj

标签图论拓扑排序

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！