Good Bye 2014 B. New Year Permutation（floyd ）

题意:给n个数，要求这n个数字小的尽量放到前面，求一个最小的。

给一个矩阵s[i][j]==1，表示位置 i 的数字可以和位置 j 的数字交换。

分析：

刚开始用的是3个循环，每次都找一个能直接连接的最小的放到前面，过了小数据，快结束的时候被hack了。

其实不应该这么做，因为还有间接相连提前交换的最小的解。正解是用floyd，先预先处理出来同一堆，也就是

直接和间接相连的所有标记，然后根据标记从前向后找最小的。

这个题也可以用并查集做，当时想到了，感觉B题的程度应该考虑暴力神马的，结果随便写了一下也没对。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #define LL __int64
 8 const int maxn = 1e3 + 10;
 9 using namespace std;
10 char s[maxn][maxn];
11 int a[maxn], f[maxn][maxn];
12 
13 int main()
14 {
15     int i, j, n, k;
16     while(~scanf("%d", &n))
17     {
18         memset(f, 0, sizeof(f));
19         for(i = 0; i < n; i++)
20         scanf("%d", &a[i]);
21         for(i = 0; i < n; i++)
22         {
23             getchar();
24             scanf("%s", s[i]);
25             for(j = 0; j < n; j++)
26             if(s[i][j]=='1')
27             f[i][j] = 1;
28         }
29 
30         for(k = 0; k < n; k++)
31         for(i = 0; i < n; i++)
32         for(j = 0; j < n; j++)
33             if(f[i][k] && f[k][j])
34                 f[i][j] = 1;
35 
36         for(i = 0; i < n; i++)
37         for(j = i+1; j < n; j++)
38         if(f[i][j] && a[i]>a[j])
39          swap(a[i], a[j]);
40 
41         for(i = 0; i < n; i++)
42         {
43             if(i == n-1) cout<<a[i]<<endl;
44             else printf("%d ", a[i]);
45         }
46     }
47     return 0;
48 }

Good Bye 2014 B. New Year Permutation（floyd ）

相关推荐