HDU2647 Reward(拓扑排序)

题目链接。

分析：

我使用结构的是边表。

1.因为只有满足偏序关系才能应用拓扑排序（即u>v要改成v<=u），所以在建立临边时要注意。

2.在拓扑排序过程中，如果发现环，那么结果便是No。

3.至于每个点的具体值，我用了一个一维数组vis来辅助标记。

AC代码如下：

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

#define MAXN 10010
#define MAXM 20010

struct node{
    int to;
    int next;
}node[MAXM];

int head[MAXN], top, n, m, indegree[MAXN], ans[MAXN], vis[MAXN];

void Init(){
    int i;
    top = 0;
    for(i=0; i<=n; i++){
        head[i] = -1;
        indegree[i] = 0;
        vis[i] = 0;
    }
}

void add(int u, int v){
    node[top].to = v;
    node[top].next = head[u];
    head[u] = top++;
}

int toposort(){
    int i, j, k;

    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(indegree[j] == 0){
                indegree[j]--;
                break;
            }
        }
        
        if(j>n) return 0;
        
        ans[i] = 888+vis[j];
        
        for(k=head[j]; k != -1; k = node[k].next){
            indegree[node[k].to]--;
            if(vis[node[k].to]<=vis[j]) vis[node[k].to] = vis[j]+1;
        }
    }
    
    return 1;
}

int main(){
    int u, v, i, sum;
    
    while(scanf("%d %d", &n, &m) == 2){
        
        Init();
        
        for(i=0; i<m; i++){
            scanf("%d %d", &u, &v);
            add(v, u);
            indegree[u]++;
        }

        sum = 0;
        
        if(toposort()){
            for(i=1; i<=n; i++) sum += ans[i];
            printf("%d\n", sum);
        }
        else printf("-1\n");

    }
    return 0;
}