`

【拓扑排序】HDU 2647 Reward【2012/3/25更新】

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=2647

题意:先给出人数n和关系数m,再给出工人之间的工资大小关系,例如给出a b表示a>b,求老板至少要给多少工资【注:工人至少有888元的工资】

Sample Input
2 1
1 2
2 2
1 2
2 1
6 5
2 4
3 6
3 5
1 2
1 3
4 3
1 2
3 4
2 3

Sample Output
1777
-1
5532
3558


#include <iostream>
#include <queue>
using namespace std;
#define M 10005

struct edge{
    int v, w, nxt;
}e[20005];

int ind[M], p[M], cnt, money[M], n;

void init ()
{
    cnt = 0;
    memset (p, -1, sizeof(p));
    memset (ind, 0, sizeof(ind));
    for (int i = 1; i <= n; i++) money[i] = 888;
}

void addedge (int u, int v)
{
    e[cnt].v = v, e[cnt].nxt = p[u], p[u] = cnt++;
}

int main()
{
    int m, u, v, i, num, ans = 0;
    while (~scanf ("%d%d", &n, &m))
    {
        init ();
        while (m--)
        {
            scanf ("%d%d", &u, &v);
            addedge (v, u);		//逆向思维
            ind[u]++;
        }
        queue<int> q;
        for (i = 1; i <= n; i++)
            if (ind[i] == 0)
                q.push (i);
        num = ans = 0;
        while (!q.empty())
        {
            u = q.front();
            q.pop();
            ans += money[u];	//累加确定工资
            num++;
            for (i = p[u]; i != -1; i = e[i].nxt)
            {
                if (--ind[e[i].v] == 0)
                {
                    money[e[i].v] = money[u] + 1;
                    q.push (e[i].v);
                }
            }
        }
        if (num < n) ans = -1;
        printf ("%d\n", ans);
    }
    return 0;
}
1
2
分享到:
评论

相关推荐

    hdu2000-2012(C++)答案

    最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的

    hdu排序练习

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

    hdu.rar_hdu

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

    HDU图论题目分类

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

    HDU题目java实现

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

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

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

    Hdu1000—2169部分代码

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

    HDU最全ac代码

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

    hdu acm2000至2099参考源码

    HDU ACM(ACM/ICPC国际大学生程序设计竞赛)是一个知名的编程竞赛平台,它提供了大量的算法题目供参赛者挑战。这些题目旨在提升参赛者的算法设计、编程和问题解决能力。"hdu acm2000至2099参考源码"是针对这个平台上...

    hdu acm 教案(3)

    HDU ACM教案是针对ACM/ICPC(国际大学生程序设计竞赛)的训练教程,旨在提升参赛者在算法和编程方面的能力。动态规划是计算机科学中一种强大的问题解决方法,尤其在处理最优化问题时非常有效。在这个教案中,我们将...

    hdu1250高精度加法

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

    HDU DP动态规划

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

    ACM HDU题目分类

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

    杭电ACMhdu1163

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

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu acm 教案(7)

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

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

Global site tag (gtag.js) - Google Analytics