首页 > 代码库 > hdu 2647 Reward (拓扑排序分层)

hdu 2647 Reward (拓扑排序分层)

2024-07-14 04:22:33   224人阅读

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.
 

 

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.
 

 

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;}

 


联系
我们