`

hdu 2647 Reward(拓扑排序)

阅读更多

Reward

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

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
 

       最经典的拓扑排序,题目大意:给你a和b,则a的功劳大于b的功劳,即a所得的报酬比要b的多,先输入n和m,表示有n个人,m种关系。报酬至少是888元,问你要分配这些报酬,至少要给多少钱?如果这些关系出现问题(出现环),输出-1。

        就是一个拓扑排序,不解释了,直接代码吧。

链接:http://acm.hdu.edu.cn/showproblem.php?pid=2647

代码:

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;

const int N = 10005;
const int M = 20005;

struct edge
{
    int w;
    edge *next;
}*e[N];

edge memory[M];
int cnt;
int deg[N], money[N];
int n, m;

void init()     //初始化
{
    cnt = 0;
    for(int i = 0; i <= n; i++)
    {
        e[i] = NULL;
        money[i] = 888;
        deg[i] = 0;
    }
}

void add(int x, int y)  //建边
{
    edge *p = &memory[cnt++];
    p->w = y;
    p->next = e[x];
    e[x] = p;
}

int main()
{
    int i, x, y, k, u, num, sum;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        init();
        sum = 0;
        num = n;
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d", &x, &y);
            add(y, x);  //建边
            deg[x]++;   //度数++
        }
        /// 拓扑排序
        queue<int> Q;
        for(i = 1; i <= n; i++)
        {
            if(deg[i] == 0) Q.push(i);
        }
        while(!Q.empty())
        {
            k = Q.front();
            Q.pop();
            num--;
            for(edge *p = e[k]; p; p = p->next) //链表代替矩阵
            {
                u = p->w;
                if(--deg[u] == 0)   //和k连接的点度数--,若为0,入队列
                {
                    money[u] = money[k] + 1;    //钱比连接点k的钱多1
                    Q.push(u);
                }
            }
        }
        if(num > 1) printf("-1\n");     //入队列次数少于n,证明有环
        else
        {
            for(i = 1; i <= n; i++)
            {
                sum += money[i];
            }
            printf("%d\n", sum);
        }
    }

    return 0;
}

 

 

 

 

0
2
分享到:
评论

相关推荐

    hdu排序练习

    标题:“hdu排序练习”与描述“hdu ACM 各种排序”共同指向了HDOJ(Hangzhou Dianzi University Online Judge)平台上的排序算法练习。HDOJ是计算机科学与技术领域内,尤其是算法设计与分析方向,非常受欢迎的一个...

    HDU图论题目分类

    本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...

    hdu.rar_hdu

    3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...

    HDU题目java实现

    7. **排序与搜索**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法,以及线性搜索、二分搜索等查找算法。 8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS...

    Hdu1000—2169部分代码

    4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。 6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU ACM 绝对值排序 txt格式

    ### HDU ACM 绝对值排序 txt格式 #### 知识点分析 ##### 1. ACM编程竞赛背景 ACM(Association for Computing Machinery)国际大学生程序设计竞赛是一项旨在展示大学生创新能力、团队精神和在压力下编写程序、...

    HDU最全ac代码

    1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小生成树、拓扑排序等)和动态规划等。 2. **数据结构**:如链表、...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    1. **基础算法**:包括排序(快速排序、归并排序等)、搜索(二分查找、深度优先搜索等)、图论(最短路径、最小生成树等)。 2. **动态规划**:解决许多具有重叠子问题和最优子结构的问题,如背包问题、最长公共子...

    杭电ACMhdu1163

    1. **算法基础**:解决ACM题目,首先需要掌握基础的算法,如排序(快速排序、归并排序、冒泡排序等)、搜索(二分查找、深度优先搜索、广度优先搜索等)和动态规划。 2. **数据结构**:常用的数据结构包括数组、...

    hdu acm 教案(7)

    9. **图的搜索算法应用**:搜索算法在图论中有广泛应用,如拓扑排序、最小生成树、最短路径等。掌握这些算法对于解决实际问题至关重要。 10. **实践与技巧**:在ACM竞赛中,除了理解理论知识,还需要熟练掌握算法的...

    hdu2101解决方案

    hdu2101AC代码

    HDU acm-PPT课件

    同时,理解算法基础如排序(冒泡、选择、插入、快速、归并等)、查找(顺序、二分、哈希等)以及递归和动态规划等,对于解决问题至关重要。 二、数据结构篇:构建解题工具箱 数据结构是ACM竞赛中的核心部分,包括...

Global site tag (gtag.js) - Google Analytics