Reward

其实就是用拓补排序判一下环，但需要注意两点：一是反向建图。这主要是为了计算奖金时的方便，因为反向建图就可以从奖金最少的那个人出发，遍历整个图，逐步累加得到答案；如果是正向建图，则需要先找到奖金最少的那个人，将他作为起点......二是这道题其实是根据每个点(人)在图中的深度来确定每个点(人)的奖金的。已下图为例：

3和4的深度是一样的，所以两者的奖金也一样。因此，不能简单地认为，如果可以拓补排序了，答案就是888 + (n * (n - 1)) / 2

代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e4+5;
int head[2*maxn];
int n,m;        //n个点,m条边 
struct edge{
    int to;
    int next;
};
int tot;
int maxi; 
edge edges[2*maxn];
int deg[2*maxn];
int dep[2*maxn];
void add_edge(int u,int v)
{
    edges[tot].to=v;
    edges[tot].next=head[u];
    head[u]=tot++;
    deg[v]++;
}
int topo()
{
    queue<int> que;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            que.push(i);
            deg[i]--;
        }
    }
    int ans=0;
    while(!que.empty())
    {    
        cnt++;
        int fro=que.front();
        ans+=(888+dep[fro]);
        que.pop();
        for(int i=head[fro];i!=-1;i=edges[i].next)
        {
            int ito=edges[i].to;
            deg[ito]--;
            if(deg[ito]==0){
                dep[ito]=dep[fro]+1;
                que.push(ito);
            }
        }
    }
    if(cnt==n)
        return ans;
    return -1;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        tot=0;mst(head,-1);
        mst(deg,0);mst(dep,0);
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            add_edge(b,a);
        }
        int rsl=topo();
        cout<<rsl<<endl;
    }
    return 0;
}