首页 > 代码库 > Good Bye 2014 B. New Year Permutation（floyd ）
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 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。