New Year Permutation

题意翻译

## 题意翻译 用户 ainta 有一个排列 $p_1,p_2,...,p_n$ 。新年到了，他希望把他的排列变得尽可能漂亮。 当且仅当存在整数 $k$（$1 \le k \le n$）使 $a_1=b_1,a_2=b_2,\ldots,a_{k-1}=b_{k-1}$ 和 $a_k<b_k$ 都成立，排列 $a_1,a_2,...,a_n$ 比 $b_1,b_2,...,b_n$ 更漂亮。 排列 $p$ 非常敏感，只可以通过交换两个不同的元素来修改它。但是交换两个不同的元素比你想象得要难。给出一个 $n\times n$ 的二进制矩阵 $A$ ，当且仅当 $A_{i,j}=1$ 时，用户 ainta 可以交换两个元素 $p_i,p_j (1<=i,j<=n,i\neq j)$ 的值。 给定排列 $p$ 和矩阵 $A$ ，用户 ainta 想知道他能得到的最漂亮的排列。 ## 输入格式 第一行包含一个整数 $n$（$1 \le n \le 300$），即排列 $p$ 的长度。 第二行包含 $n$ 个由空格分开的整数 $p_1,p_2,...,p_n$ ，保证每个不同的整数只出现一次。 接下来 $n$ 行描述矩阵 $A$ 。保证 $A_{i,j}=A_{j,i}$（$1 \le i<j \le n$）和 $A_{i,i}=0$（$1 \le i \le n$）。 ## 输出格式 一行 $n$ 个空格分隔的整数，表示得到的最漂亮的排列。

题目描述

User ainta has a permutation $ p_{1},p_{2},...,p_{n} $ . As the New Year is coming, he wants to make his permutation as pretty as possible. Permutation $ a_{1},a_{2},...,a_{n} $ is prettier than permutation $ b_{1},b_{2},...,b_{n} $ , if and only if there exists an integer $ k $ ( $ 1<=k<=n $ ) where $ a_{1}=b_{1},a_{2}=b_{2},...,a_{k-1}=b_{k-1} $ and $ a_{k}&lt;b_{k} $ all holds. As known, permutation $ p $ is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an $ n×n $ binary matrix $ A $ , user ainta can swap the values of $ p_{i} $ and $ p_{j} $ ( $ 1<=i,j<=n $ , $ i≠j $ ) if and only if $ A_{i,j}=1 $ . Given the permutation $ p $ and the matrix $ A $ , user ainta wants to know the prettiest permutation that he can obtain.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=300 $ ) — the size of the permutation $ p $ . The second line contains $ n $ space-separated integers $ p_{1},p_{2},...,p_{n} $ — the permutation $ p $ that user ainta has. Each integer between $ 1 $ and $ n $ occurs exactly once in the given permutation. Next $ n $ lines describe the matrix $ A $ . The $ i $ -th line contains $ n $ characters '0' or '1' and describes the $ i $ -th row of $ A $ . The $ j $ -th character of the $ i $ -th line $ A_{i,j} $ is the element on the intersection of the $ i $ -th row and the $ j $ -th column of A. It is guaranteed that, for all integers $ i,j $ where $ 1<=i&lt;j<=n $ , $ A_{i,j}=A_{j,i} $ holds. Also, for all integers $ i $ where $ 1<=i<=n $ , $ A_{i,i}=0 $ holds.

输出格式

In the first and only line, print $ n $ space-separated integers, describing the prettiest permutation that can be obtained.

输入输出样例

输入样例 #1

7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

输出样例 #1

1 2 4 3 6 7 5

输入样例 #2

5
4 2 1 5 3
00100
00011
10010
01101
01010

输出样例 #2

1 2 3 4 5

说明

In the first sample, the swap needed to obtain the prettiest permutation is: $ (p_{1},p_{7}) $ . In the second sample, the swaps needed to obtain the prettiest permutation is $ (p_{1},p_{3}),(p_{4},p_{5}),(p_{3},p_{4}) $ . A permutation $ p $ is a sequence of integers $ p_{1},p_{2},...,p_{n} $ , consisting of $ n $ distinct positive integers, each of them doesn't exceed $ n $ . The $ i $ -th element of the permutation $ p $ is denoted as $ p_{i} $ . The size of the permutation $ p $ is denoted as $ n $ .