codeforces 500 B. New Year Permutation

2015年12月5日 0 作者 CrazyKK

http://codeforces.com/contest/500/problem/B

题意:给定一个1至n的数的一种排列。给定一个n*n的矩阵,a[i][j]==0代表pi,pj不可以交换,a[i][j]为1代表p[i],p[j]可以交换。 问字典序最小的排列。。

 

思路:把矩阵看成图的关系。。反正n很小。。跑一遍floyd..得到可以间接交换的点。。然后冒泡排序就好。。只有p[i]>p[j]并且a[i][j]的时候交换。