欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU2647,拓扑排序

程序员文章站 2022-05-01 14:27:20
...

题目链接:Reward
如果a要比b的钱多的话,就要在b的奖金的基础上增加至少1元钱,为了能够花费最少,我们当然是选择增加1元钱。
这道题呢,跟裸的拓扑排序题稍微有点区别。我下面讲讲我的做题的过程(WA到哭的过程…)
我首先想,不就是一个拓扑排序嘛,然后就按照通常的做法,拓扑排序,排好之后比如有4个,那么总和就为888+889+890+891,然后提交之后,wa了。
然后我就想到一种情况,比如1大于2,3大于2,那么最少的钱不就是888+889*2嘛,然后我就改了一下,从最下层做起,记录每一层的数量,比如刚刚1>2,3>2,那么第一层就是2,第二层就是1,3,然后将第一层作为基础,也就是888,然后计算总和,提交后还是wa了。
再然后,我想到了另一种情况,如下图:HDU2647,拓扑排序

在这张图片中,本来应该以5,6,7为第一层,3,1,4为第二层,2为第三层,但如果按照刚刚的思路,那么2,3为一层,1,4,6,7为第二层,5为第三层,所以会错。所以正确的做法应该是逆向建图,这样就能保证答案的正确了。
逆向建图之后应该是这样:
HDU2647,拓扑排序
代码如下:

/*************************************************************************
    > File Name: main.cpp
    > Author:Eagles 
    > Mail:None 
    > Created Time: 2018年09月16日 星期日 18时08分58秒
    > Description:HDU2647
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
#define N 50005
struct node
{
    int to;
    int nex;
}E[N*2];
int head[N];
int in_deg[N];
int n,m;
int cnt;
queue<int>q;
int layer[N];//记录每一层的数量

bool addEdge(int a, int b)
{
    for (int i=head[a]; i!=-1; i=E[i].nex)//判断重边
    {
        if (E[i].to ==b)
            return false;
    }

    E[cnt].to=b;
    E[cnt].nex=head[a];
    head[a]=cnt++;
    return true;
}

void init()
{
    fill(head,head+N,-1);
    fill(in_deg,in_deg+N,0);
    cnt=0;
    while (!q.empty())
        q.pop();

    for (int i=0; i<m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if (addEdge(b,a))
            in_deg[a]++;
    }
}

void topsort()
{
    int sum=0;
    int num=0;

    for (int i=1; i<=n; i++)
    {
        if (!in_deg[i])
            q.push(i);
    }

    while (!q.empty())
    {
        int the_size=q.size();

        layer[sum++]=the_size;//每一层的数量

        for (int i=0; i<the_size; i++)
        {
            int cur=q.front();
            q.pop();
            num++;//用来判断是否能够拓扑排序
            for (int j=head[cur]; j!=-1; j=E[j].nex)
            {
                in_deg[E[j].to]--;
                if (in_deg[E[j].to]==0)
                    q.push(E[j].to);
            }
        }

    }

    if (num==n)
    {

        int money=0;

        for (int i=0; i<sum; i++)
        {
            money+=(888+i)*layer[i];//每一层的钱
        }

        printf("%d\n",money);
    }
    else
        printf("-1\n");
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        init();
        topsort();
    }
    return 0;
}

wa了很多次,被自己菜哭了

相关标签: 图论 拓扑排序