HDOJ 2647 Reward（分层拓扑排序）

超级传送门

分层的拓扑排序，先判断是否有环，然后再逆过来求拓扑排序,即设置两张邻接表，一张存前驱，一张存后继，判断有环没还用前驱表，判断至少要多少工资用后继表。

算法写得不好，C++能过（约500MS），但是GNU C++超时了，目前不知道原因，求大神指教。

下附代码：

[cpp]
/*HDOJ2647
作者：陈佳润
2013-04-26
*/
#include<stdio.h>
#include<queue>
using namespace std;

typedef struct tag{
    int person;
    struct tag *next;
}Node;
typedef struct tag1{
    int num;
    Node *list;
}List;

queue<int>Q;

int TopologicalOrder(List L[],int n){//拓扑排序，用来判断是否有环
    int i,j,a,sum=0;
    for(i=1;i<=n;i++){//对于每一个点
        for(j=1;j<=n;j++){//遍历一次，找出一个适合的点
            if(L[j].num==0){//当找到一个点没有前驱
                L[j].num--;//减1成为-1，这样下次不会找到
                sum++;
                while(L[j].list){//它的后继点的前驱结点数目都减1
                    a=L[j].list->person;
                    L[a].num--;
                    L[j].list=L[j].list->next;
                }
                break;
            }
        }
    }
    return sum==n;
}

int main(){
    List L[10005],BL[10005];//L是后继表，BL是前驱表
    int n,m,i,a,b,j;
    int k;
    int account;
    Node *p;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++){//初始化
            L[i].num=BL[i].num=0;
            L[i].list=BL[i].list=NULL;
        }
        //读入
        for(i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            p=new Node;
            //构造前驱表
            BL[b].num++;
            p->person=b;
            p->next=BL[a].list;
            BL[a].list=p;
            //构造后继表
            p=new Node;
            L[a].num++;
            p->person=a;
            p->next=L[b].list;
            L[b].list=p;
        }
        //判断是否有环
        if(TopologicalOrder(BL,n)==0){
            printf("-1\n");
            continue;
        }
        //逆拓扑排序计算费用
        account=n*888;
        k=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(L[j].num==0){
                    account+=k;
                    Q.push(j);
                    L[j].num--;
                }
            }
            k++;
            while(!Q.empty()){
                int t=Q.front();
                Q.pop();
                while(L[t].list){
                    L[L[t].list->person].num--;
                    L[t].list=L[t].list->next;
                }
            }

        }
        printf("%d\n",account);
    }
    return 0;
}

补充：软件开发 , C++ ,