首页 > 代码库 > codeforces 500B.New Year Permutation 解题报告
codeforces 500B.New Year Permutation 解题报告
题目链接：http://codeforces.com/problemset/problem/500/B
题目意思：给出一个含有 n 个数的排列：p1, p2, ..., pn-1, pn。紧接着是一个 n * n 的矩阵A，当且仅当 Aij = 1 时，pi 与 pj 可以交换数值。现在问如何交换数值，使得最后得到的排列字典序最小。
比赛的时候不会做，看了Tutorial 1 的解法，觉得别人做得太巧妙了，出题者也出得很好 ^_^
可以看这个：http://codeforces.com/blog/entry/15488
它是利用了并查集来做的。如果遇到 Aij = 1 的话，就将点 i 和 点 j 连一条边。最终会得到一些互不相交的集合。以第一组 test 来说吧～～～
这就表示位置 1、4、7 的数是可以交换的，位置 2、5 要保持原封不动，位置 3、6 的数可以交换。由于每个集合都有一个祖先，即第一层的那个数，依次为 7、2、5、6，然后就把每个集合的数放到以该集合祖先为首的 vector 数组里面，并把每个集合内的数从小到大排序。最后遍历位置 1 ～ n，根据每个位置的数所属的集合（以哪个祖先为首），依次输出。
只能说，解题思路真是太巧妙兼神奇！竟然可以转化成图！继续干爸爹吧 ^_^
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 300 + 10; 9 int p[maxn], cnt[maxn];10 int group[maxn];11 char s[maxn];12 vector<int> vi[maxn];13 14 int find(int x)15 {16 if (x == group[x])17 return x;18 return group[x] = find(group[x]);19 }20 21 void merge(int x, int y)22 {23 int fx = find(x);24 int fy = find(y);25 if (fx != fy)26 group[fx] = fy;27 }28 29 int main()30 {31 #ifndef ONLINE_JUDGE32 freopen("in.txt", "r", stdin);33 #endif // ONLINE_JUDGE34 int n;35 while (scanf("%d", &n) != EOF)36 {37 vi[n].clear();38 for (int i = 1; i <= n; i++) {39 scanf("%d", &p[i]);40 group[i] = i;41 }42 for (int i = 1; i <= n; i++) {43 scanf("%s", s+1);44 for (int j = 1; j <= n; j++) {45 if (s[j] == ‘1‘) {46 merge(i, j);47 }48 }49 }50 for (int i = 1; i <= n; i++) {51 vi[find(i)].push_back(p[i]); // 千万不要写成 vi[group[i]].push_back(p[i]);52 }53 for (int i = 1; i <= n; i++) {54 sort(vi[i].begin(), vi[i].end());55 }56 memset(cnt, 0, sizeof(cnt));57 for (int i = 1; i <= n; i++) {58 int g = group[i];59 printf("%d%c", vi[g][cnt[g]++], i == n ? ‘\n‘ : ‘ ‘);60 }61 }62 return 0;63 }
注意，代码中的 51 行的部分，如果写成 vi[group[i]].push_back(p[i]) 是错的！以第二个 test 为例，group[1] = 3，find[1] = 5。find[i] 才会找到最终的祖先！！！
codeforces 500B.New Year Permutation 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。