首页 > 代码库 > HDU2647 Reward 【拓扑排序】

HDU2647 Reward 【拓扑排序】

2024-07-15 10:02:59   224人阅读

Reward

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3927    Accepted Submission(s): 1199


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 1
1 2
2 2
1 2
2 1
 

Sample Output
1777
-1
题意：有n个员工，有些员工要求自己的奖金要比另外的一些高，求至少发放多少奖金能满足所有人的要求，若没法满足就输出-1；

题解：可以把每个人的需求想象成层数，若没有需求就在第一层，奖金一层层的发，每增加一层就加一块钱，这样就能满足最终发的奖金数额最小。需要逆序拓扑，另外这题碰到了个奇怪的现象，开始我的map数组开小了，但是提交的时候给的结果是TLE而不是RE，把数组加了一倍后就AC了，看来OJ判题系统并不是太精确。

#include <stdio.h>
#include <string.h>
#define maxn 10002

int ans, queue[maxn];
struct Node{
    int to, next, val;
} map[maxn << 1];
struct node{
    int first, money, indegree;
} head[maxn];

bool topoSort(int n)
{
    int i, front = 0, back = 0, u;
    for(i = 1; i <= n; ++i)
        if(!head[i].indegree) queue[back++] = i;
    while(front != back){
        u = queue[front++];
        ans += head[u].money;
        for(i = head[u].first; i != 0; i = map[i].next)
            if(!--head[map[i].to].indegree){
                head[map[i].to].money = head[u].money + 1;
                queue[back++] = map[i].to;
            }
    }
    return back == n;
}

int main()
{
    int n, m, a, b, i;
    while(scanf("%d%d", &n, &m) != EOF){
        memset(head, 0, sizeof(head));
        for(i = 1; i <= m; ++i){
            scanf("%d%d", &a, &b);
            map[i].to = a;
            map[i].next = head[b].first;
            ++head[a].indegree;
            head[b].first = i;
        }
        ans = 888 * n;
        if(!topoSort(n)) printf("-1\n");
        else printf("%d\n", ans);
    }
    return 0;
}


联系
我们