首页 > 代码库 > hdu 2647 Reward (拓扑排序分层)
hdu 2647 Reward (拓扑排序分层)
Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3815 Accepted Submission(s): 1162
Problem Description
Dandelion‘s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a‘s reward should more than b‘s.Dandelion‘s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work‘s reward will be at least 888 , because it‘s a lucky number.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a‘s reward should more than b‘s.Dandelion‘s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work‘s reward will be at least 888 , because it‘s a lucky number.
Input
One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a‘s reward should be more than b‘s.
then m lines ,each line contains two integers a and b ,stands for a‘s reward should be more than b‘s.
Output
For every case ,print the least money dandelion ‘s uncle needs to distribute .If it‘s impossible to fulfill all the works‘ demands ,print -1.
Sample Input
2 11 22 21 22 1
Sample Output
1777-1
题意:就是老板要给员工发福利,每个人的贡献不一样,,老板就要根据贡献来进行发福利了,但是老板又想最少的发福利,每个人基本福利是888,若A比B的贡献大,那我们就给A发889。
解题思路:如果用邻接矩阵来做的话,我觉得肯定是要超内存的,所以我选择了用邻接表来处理这一道题。因为是要比较谁比谁大,进行统计,所以我们就反方向的来建图,这样就可以统计出来在每一个层次的人。这样做还是WA了一次,因为一个人可能比多个人贡献要大,所以我们要选取他比那多个人中最大的那个人要多就够了,嘿嘿。
贴出代码:
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10005struct ArcNode{ int to; struct ArcNode * next;};struct ArcNode * List[MAXN];int counting[MAXN], Indegree[MAXN];int mark;void Topological(int n){ int top = -1; struct ArcNode * temp; for(int i = 1; i<=n; i++) //将度为0的点入栈 { if(0 == Indegree[i]) { Indegree[i] = top; top = i; } } for(int i = 1; i<=n; i++) { if(top == -1) //判断是否构成环 { mark = 1; break; } else { int j = top; top = Indegree[top]; temp = List[j]; while(NULL != temp) { int k = temp->to; counting[k] = counting[k] > counting[j]+1 ? counting[k] : counting[j]+1; //取最大的贡献 if(--Indegree[k] == 0) { Indegree[k] = top; top = k; } temp = temp->next; } } }}int main(){ int n, m, u, v, num; struct ArcNode * temp; while(scanf("%d%d", &n, &m)!=EOF) { memset(counting, 0, sizeof(counting)); memset(Indegree, 0, sizeof(Indegree)); memset(List, 0, sizeof(List)); mark = 0; num = 0; while(m--) { scanf("%d%d", &u, &v); //u表示起点,v表示终点 Indegree[u]++; //反向建图,记录每个点的入度 temp = (struct ArcNode *)malloc(sizeof(ArcNode)); temp->to = u; temp->next = NULL; if(List[v] == NULL) List[v] = temp; else { temp->next = List[v]; List[v] = temp; } } Topological(n); if(mark) printf("-1\n"); else { for(int i = 1; i<=n; i++) //将各个点的值累加 num += counting[i]; num = num+888*n; printf("%d\n", num); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。