链接： , 不算复杂的拓扑排序。
这道题不复杂，有一点需要考虑的就是当前保存在队列首的顶点的边删去时，会产生新的入度为0的顶点，这时产生的新的入度为0的顶点要比队列首的顶点要高一级，就是工资比他多1，这点处理就没什么事情了。
#include#include #include #include #include #include #include #include using namespace std;#define LL __int64#define eps 1e-8#define INF 1e8#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int MOD = 2333333; const int maxn = 10000 + 5;int Rank[maxn] , degree[maxn];vector graph[maxn];int n , m;bool toposort(){ int i , j , u , v , tot; tot = 0; memset(Rank , 0 , sizeof(Rank)); memset(degree , 0 , sizeof(degree)); for(int i = 1 ; i <= n ; i++) for(int j = 0 ; j < graph[i].size() ; j++) degree[ graph[i][j] ] ++; queue que; for(int i = 1 ; i <= n ; i++) { if(degree[i] == 0) { que.push(i); Rank[i] = 0; tot++; } } while(!que.empty()) { int u = que.front(); que.pop(); for(int i = 0 ; i < graph[u].size() ; i++) { int tmp = graph[u][i]; degree[tmp]--; if(degree[tmp] == 0) { que.push(tmp); Rank[tmp] = Rank[u] + 1; //就是这里，工资要多1 tot++; } } } return tot == n;}int main(){ int a , b; while(~scanf("%d %d" , &n , &m)) { for(int i = 1 ; i <= n ; i++) graph[i].clear(); while(m--) { scanf("%d %d" , &a , &b); graph[b].push_back(a); } if(toposort()) { int res = 888 * n; for(int i = 1 ; i <= n ; i++) res += Rank[i]; printf("%d\n" , res); } else { printf("-1\n"); } } return 0;}