Day4 - G - 确定比赛名次 HDU

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。
Output给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
Sample Input

Sample Output

1 2 4 3

思路：直接拓扑排序即可，输出要求字典序最小，那么DFS就不行，无法保证字典序，直接上优先队列，代码如下：
插一手DFS代码(无字典序)

const int maxm = ;

int G[maxm][maxm], vis[maxm], N, M;

vector<int> ans;

bool dfs(int x) {

    vis[x] = -;

    for (int i = ; i <= N; ++i) {

        if(G[x][i]) {

            if(vis[i] == -)

                return false;

            if(!vis[i] && !dfs(i))

                return false;

        }

    }

    vis[x] = ;

    ans.push_back(x);

    return true;

}

int main() {

    while(scanf("%d%d",&N,&M) != EOF) {

        memset(G, , sizeof(G)), ans.clear(), memset(vis, , sizeof(vis));

        for (int i = ; i < M; ++i) {

            int t1,t2;

            scanf("%d%d", &t1, &t2);

            G[t1][t2] = ;

        }

        for(int i = ; i <= N; ++i)

            if(!vis[i])

                if(!dfs(i))

                    break;

        int cnt = ;

        for (auto i = ans.rbegin(); i != ans.rend(); ++i) {

            if(cnt++)

                printf(" ");

            printf("%d", *i);

            if(cnt == N)

                break;

        }

    }

    return ;

}

AC代码：

const int maxm = ;

int N, M, in[maxm], G[maxm][maxm], ans[maxm], cnt;

struct Node {

    int id;

    Node(int _id) : id(_id){}

    bool operator<(const Node &a) const {

        return a.id < id;

    }

};

int main() {

    while(scanf("%d%d", &N, &M) != EOF) {

        memset(in, , sizeof(in)), memset(G, , sizeof(G)), cnt = ;

        for (int i = ; i < M; ++i) {

            int t1, t2;

            scanf("%d%d", &t1, &t2);

            if(!G[t1][t2]) {

                G[t1][t2] = ;

                in[t2]++;

            }

        }

        priority_queue<Node> q;

        for (int i = ; i <= N; ++i) {

            if(!in[i])

                q.push(Node(i));

        }

        while(!q.empty()) {

            Node p = q.top();

            q.pop();

            int u = p.id;

            ans[cnt++] = u;

            for (int i = ; i <= N; ++i) {

                if(G[u][i]) {

                    if(!--in[i])

                        q.push(Node(i));

                }

            }

        }

        for(int i = ; i < N; ++i) {

            if(i)printf(" ");

            printf("%d", ans[i]);

        }

        printf("\n");

    }

    return ;

}

注意读入判重，否则会影响入度的计算。

巴特西

Day4 - G - 确定比赛名次 HDU - 1285

最新文章

热门文章