Good Bye 2014 B. New Year Permutation（floyd ）

题目链接

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

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

分析：

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

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

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

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

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #define LL __int64

 const int maxn = 1e3 + ;

 using namespace std;

 char s[maxn][maxn];

 int a[maxn], f[maxn][maxn];

 int main()

 {

     int i, j, n, k;

     while(~scanf("%d", &n))

     {

         memset(f, , sizeof(f));

         for(i = ; i < n; i++)

         scanf("%d", &a[i]);

         for(i = ; i < n; i++)

         {

             getchar();

             scanf("%s", s[i]);

             for(j = ; j < n; j++)

             if(s[i][j]=='')

             f[i][j] = ;

         }

         for(k = ; k < n; k++)

         for(i = ; i < n; i++)

         for(j = ; j < n; j++)

             if(f[i][k] && f[k][j])

                 f[i][j] = ;

         for(i = ; i < n; i++)

         for(j = i+; j < n; j++)

         if(f[i][j] && a[i]>a[j])

          swap(a[i], a[j]);

         for(i = ; i < n; i++)

         {

             if(i == n-) cout<<a[i]<<endl;

             else printf("%d ", a[i]);

         }

     }

     return ;

 }