HDU 2647 Reward（拓扑排序）

题目链接：Click here~~

题意：

老板给员工发薪水，有的员工要求必须比某些员工薪水高。基础薪水是888，问最少发多少薪水。

解题思路：

想要发的薪水最少，就要让员工尽量只满足要求即可，不必多发。

我们可以大致想象出员工的薪水大概是一层一层分布的，即888一层，889一层，依此类推，每层有若干个员工，但一定不会为0。（想想为什么）

接下来，我们将员工依次从底层向上安排。

第一层的人肯定是那些没有要求的员工，因为他们对工资没有要求。

安排完第一层后，那些要求比第一层员工工资高的员工要求已经满足，我们可以将这些已经满足的要求删除掉，然后继续找当前没有工资要求的员工，放入第二层。

依此类推。

我们发现，上述思路和拓扑排序极为相似。于是反向建图后，稍加修改即可得到此题的解。

ps:又进rank了，囧。

#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define N 10005

struct T
{
    int v,next;
}E[N+N];

struct TT
{
    int head,rd,dep;
}V[N];

int top,ans,n,m;

void Add_Edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
    ++V[v].rd;
}

bool Top_Sort()
{
    queue<int> Q;
    int cnt = 0;
    for(int i=1;i<=n;i++)
        if(V[i].rd == 0)
            Q.push(i);
    while(!Q.empty())
    {
        ++cnt;
        int p = Q.front();
        ans += V[p].dep;
        for(int i=V[p].head;i!=NULL;i=E[i].next)
        {
            int q = E[i].v;
            --V[q].rd;
            if(V[q].rd == 0)
            {
                Q.push(q);
                V[q].dep = V[p].dep + 1;
            }
        }
        Q.pop();
    }
    return cnt == n;
}
int main()
{
    int u,v;
    while(~scanf("%d%d",&n,&m))
    {
        memset(V,0,sizeof(V));
        top = 1; ans = 0;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            Add_Edge(v,u);
        }
        printf("%d\n",Top_Sort() ? 888*n+ans : -1);
    }
    return 0;
}