HDU - 4948 Kingdom 拓扑排序

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Description

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

Output

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

Sample Input

3
011
001
000
0

Sample Output

1 2 3

题目大意

给出一个n*n的矩阵,其中第i行第j列若为1表示城市i到城市j有一条有向边,0则代表无边,任意两城市由一条有向边连接。现在要重建城市,要求重建当前重建的城市与已经重建过的城市的距离不能超过2(注意有向),求出重建城市的编号顺序。


题解

拓扑排序删点
但是这道题和普通的拓扑排序又有不一样的地方,它要求当前重建的城市不得距离已重建城市的有向距离超过2,所以不能采取每次删除入度为0的点的方法。
这道题应该倒过来想,每次删除入度最大的点。
这样做的正确性是可以证明的:
我们采取反正法:如果从节点v到u的路径是v-a-b-u,且u为入度最大的节点,那么v就不可能会连接到u、b以及与直接连接到u的节点(否则v到u就可以满足题目条件了)。那么既然如此,又由于每两个点之间一定有一条有向边相连,所以直接上述节点一定有边直接连向v的有向边,则v的入度至少为u的入度+2,这与u为入度最大的点矛盾,于是就可以证明这种做法的正确性。
注意:删点的顺序是重建城市顺序的逆序。


题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int mp[maxn][maxn];
int ans[maxn],d[maxn];
int n;
int cnt;
int main(){
    while(true){
        scanf("%d",&n);
        if(n == 0)break;
        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                mp[i][j] = 0;
        for(int i = 1;i <= n;++i){
            ans[i] = 0;
            d[i] = 0;
        }
        cnt = n;
        getchar();
        for(int i = 1;i <= n;++i){
            for(int j = 1;j <= n;++j){
                char ch;
                scanf("%c",&ch);
                mp[i][j] = (int)(ch - '0');
                if(mp[i][j])d[j]++;
            }
            getchar();
        }
        while(cnt != 0){
            int mx = -1;
            int pos = -1;
            for(int i = 1;i <= n;++i){
                if(mx < d[i]){
                    mx = d[i];
                    pos = i;
                }
            }
            ans[cnt--] = pos;
            d[pos] = -1;
        }
        for(int i = 1;i <= n;++i)
            printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00