UVA - 12263 Rankings 模拟（拓扑排序）

题意：1~n这n个数，给你一个初始的顺序，再告诉你那两个数的大小关系发生了变化，求变化后的顺序，不存在则输出IMPOSSIBLE

思路：这题很遗憾没在比赛的时候过掉，结束后加了一行就AC了。题目真的不难，我就是根据原顺序和变化得到任意两个数之间的大小关系。然后枚举变化后的这些数对，用构造法构造一个合法的序列，最后再和原顺序进行不重复的合并。两个数组，两个指针，合并的时候未发生变化的当前数若大于变化的当前数，则输出原数，否则输出变化后的数，并将对应数组指针后移。再对得到的新顺序进行合法判断，若大小关系和要求的完全一致，则输出答案，否则无解。

这题还有更简单的拓扑排序做法，我正在研究，稍后更新。

 #pragma comment(linker, "/STACK:1000000000")

 #include <bits/stdc++.h>

 #define LL long long

 #define INF 0x3f3f3f3f

 #define IN freopen("E.in","r",stdin);

 #define OUT freopen("out.txt", "w", stdout);

 using namespace std;

 #define MAXN 505

 #define MAXM 25005

 int s[MAXM], t[MAXM];

 int a[MAXN], b[MAXN], pos[MAXN], c[MAXN];

 bool dayu[MAXN][MAXN], res[MAXN][MAXN], u[MAXN][MAXN];

 bool vis[MAXN];

 int main()

 {

     int T;

     scanf("%d", &T);

     int cas = ;

     while(T--){

         cas++;

         int n;

         scanf("%d", &n);

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

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

         }

         memset(dayu, , sizeof(dayu));

         memset(vis, , sizeof(vis));

         memset(b, , sizeof(b));

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

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

                 dayu[a[i]][a[j]] = true;

             }

         }

         int m;

         scanf("%d", &m);

         memset(u, , sizeof(u));

         for(int i = ; i <= m; i++){

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

             if(u[s[i]][t[i]]) continue;

             u[s[i]][t[i]] = true;

             dayu[s[i]][t[i]] = !dayu[s[i]][t[i]];

             dayu[t[i]][s[i]] = !dayu[t[i]][s[i]];

         }

         int x, y;

         int p = ;

         bool noans = false;

         for(int i = ; i <= m; i++){

             if(dayu[s[i]][t[i]]){

                 x = t[i];

                 y = s[i];

             }else{

                 x = s[i];

                 y = t[i];

             }

             if(!vis[x]){

                 vis[x] = true;

                 int j = p;

                 if(p == ){

                     b[++p] = x;

                 }

                 else{

                     while(j >=  && dayu[x][b[j]]){

                         j--;

                     }

                     for(int k = p; k > j; k--){

                         pos[b[k]]++;

                         b[k + ] = b[k];

                     }

                     b[j + ] = x;

                     p++;

                 }

                 pos[x] = j + ;

             }

             if(!vis[y]){

                 vis[y] = true;

                 int j = pos[x] - ;

                 while(j >=  && dayu[y][b[j]]){

                     j--;

                 }

                 for(int k = p; k > j; k--){

                     pos[b[k]]++;

                     b[k + ] = b[k];

                 }

                 p++;

                 b[j + ] = y;

                 pos[y] = j + ;

             }

         }

         int j = ;

         memset(pos, , sizeof(pos));

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

             if(vis[a[i]]){

                 c[i] = b[j++];

             }

             else{

                 if(dayu[a[i]][b[j]] || j > p){

                     c[i] = a[i];

                 }

                 else{

                     c[i] = b[j++];

                 }

             }

             pos[c[i]] = i;

         }

         memset(res, , sizeof(res));

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

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

                 res[c[i]][c[j]] = true;

             }

         }

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

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

                 if(res[i][j] != dayu[i][j]){

                     noans = true;

                     break;

                 }

             }

             if(noans){

                 break;

             }

         }

         if(noans){

             printf("IMPOSSIBLE\n");

             continue;

         }

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

             printf("%d ", c[i]);

         }

         printf("%d\n", c[n]);

     }

     return ;

 }

巴特西

UVA - 12263 Rankings 模拟（拓扑排序）

最新文章

热门文章