HDOJ 2647 Reward(トポロジーソート)

スーパーゲート:http://acm.hdu.edu.cn/showproblem.php?pid=2647
この問題は典型的なトポロジーソートですが、ソート中にノードを階層化する必要があります.トポロジーソートはゼロ入度ノードを消去する方法を採用し、階層化する際に注意しなければならない:ノードを消去する場合、そのサブノードは次の層に属し、配列is_next[]はタグ付けを行い,階層的混乱を防止する(ここでは複数のWAに寄与する).また、計算結果を容易にするためには、a->bをb->aに置き換えることが望ましい.これにより、第1階のノード従業員は基本給888であり、第n階の給与数は888+n-1であり、各階の従業員数を乗じると、最小限の支払い額が得られる.トポロジーソートが完了しても最後に残りのノードが消去されていない場合は、残りのノードがループを構成し、問題が解けず、「-1」が出力されることを示します.
コードは次のとおりです.

#include<stdio.h>
#include<string.h>
#define N 10005
#define M 20005
int n,m;
int w[N][20],num[N],r[N],vis[N],div[N],d_num,is_next[N];
int main () {
    int i,j,k,h,a,b,ans,cur,ok;
    while (scanf("%d%d",&n,&m) != EOF) {
        memset(num,0,sizeof(num));
        memset(vis,0,sizeof(vis));
        memset(r,0,sizeof(r));
        memset(div,0,sizeof(div));
        for (i=1;i<=m;i++) {
            scanf("%d%d",&a,&b);
            w[b][++num[b]] = a;
            r[a] ++;
        }
        d_num = 0;
        for (k=1;k<=n;k++) {
            ++d_num;
            memset(is_next,0,sizeof(is_next));
            for (i=1;i<=n;i++) {
                if (!r[i] && !vis[i] && !is_next[i]) {
                    ok = 1;
                    for (j=1;j<=num[i];j++) {
                        r[w[i][j]] --;
                        if (r[w[i][j]]<0) r[w[i][j]] = 0;
                        is_next[w[i][j]] = 1;
                    }
                    vis[i] = 1;
                    div[d_num]++;
                }
            }
        }
        ok = 1;
        cur = 888;
        ans = 0;
        for (i=1;i<=n;i++) {
            if (!vis[i]) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            for (i=1;i<=d_num;i++) {
                if (div[i]) {
                    ans += div[i]*cur++;
                }
            }
            printf("%d
",ans);
        } else printf("-1
");
    }
    return 0;
}