111qqz的小窝

老年咸鱼冲锋!

codeforces 500 B. New Year Permutation

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]的时候交换。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363