Codeforces Round #812 (Div. 2) E（并查集）

种类并查集：定义种类之间的关系来判断操作是否进行

题目大意：对于题目给出的一个矩阵，我们可以进行一种操作：swap(a[i][j],a[j][i])

使得矩阵可以变换为字典序最小的矩阵

思路：

　　通过扫描整个矩阵，每次都判断a[i][j] 和 a[j][i]是否需要交换

　　交换的前提就是：对第i行/第j列操作，如果既对第 i 行又第 j 列进行操作等于没交换

　　所以我们可以将 i 和 j定义为敌人，当他们是敌人的时候，说明需要交换

　　而他们是朋友的时候就说明无需交换

　　这里就涉及到种类并查集了，我们定义一个2*n的数组，如果i 和 j 是敌人：

　　　　merge( i , j+n );

　　　　merge( i+n , j );

　　这样在查询时如果find(i)>n说明i与另外一个元素有敌对关系，可以进行交换

　　否则如果是朋友：

　　　　merge( i , j );

　　　　merge( i+n , j+n );

　　find(i) <= n 说明他们为朋友关系，不可以交换

 1 # include<iostream>

 2 # include<bits/stdc++.h>

 3 using namespace std;

 4 # define int long long

 5 # define endl "\n"

 6 const int N = 2e5 + 10;

 7 int a[1010][1010];

 8 int f[1010 << 1];

 9 vector<int> siz(1010 << 1);

10 int find(int x) {

11     if (f[x] == x) return x;

12     else return find(f[x]);

13 }

14

15 void merge(int a, int b) {

16     int x = find(a);

17     int y = find(b);

18     if (x != y) {

19         if(siz[x]>siz[y]) swap(x,y);

20         f[x] = y;

21         siz[y] += siz[x];

22     }

23 }

24 void solve() {

25     int n;

26     cin >> n;

27     for (int i = 1; i <= n; ++i)

28         for (int j = 1; j <= n; ++j)

29             cin >> a[i][j];

30     for (int i = 1; i <= 2 * n; ++i) {

31         f[i] = i;

32         siz[i] = 1;

33     }

34     for (int i = 1; i <= n; ++i)

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

36             if (a[i][j] > a[j][i]) {

37                 int x = find(i), y = find(j);

38                 if (x == y) continue;

39                 merge(i, j + n);

40                 merge(i + n, j);

41             } else if (a[i][j] < a[j][i]) {

42                 int x = find(i), y = find(j + n);

43                 if (x == y) continue;

44                 merge(i, j);

45                 merge(i + n, j + n);

46             }

47         }

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

49         if (find(j) > n) continue;

50         for (int i = 1; i <= n; ++i) swap(a[i][j], a[j][i]);

51     }

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

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

54             cout << a[i][j] << " ";

55         }

56         cout << endl;

57     }

58

59 }

60 int tt;

61 signed main() {

62     ios::sync_with_stdio(false);

63     cin.tie(0);

64     cout.tie(0);

65     cin >> tt;

66     while (tt--)solve();

67

68

69     return 0;

70 }

需要注意的是，因为要求字典序最小，所以要求优先满足之前的关系，所以在每次维护关系的时候

需要先对之前的关系进行判断。

巴特西

Codeforces Round #812 (Div. 2) E（并查集）

最新文章

热门文章