CF1713E

发表于 更新于 本文字数： 209 阅读时长 ≈ 1 分钟

右上角的元素重要性大于左下角的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int tt, n;

struct dsu
{
    dsu(int n)
    {
        p.resize(n + 1);
        s.resize(n + 1);
        for (int i = 1; i <= n; i++)
            p[i] = i, s[i] = 1;
    }
    vector<int> p, s;
    int find(int x)
    {
        if (x != p[x])
            p[x] = find(p[x]);
        return p[x];
    }
    void merge(int x, int y)
    {
        int u = find(x), v = find(y);
        if (u != v)
        {
            p[v] = u;
            s[u] += s[v];
        }
    }
};

void solve()
{
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    dsu d(2 * n);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];

    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(a[i][j]>a[j][i]){
                if(d.find(i)!=d.find(j)){
                    d.merge(i,j+n);
                    d.merge(j,i+n);
                    swap(a[i][j],a[j][i]);
                }
            }else if(a[i][j]<a[j][i]){
                if(d.find(i)!=d.find(j+n)){
                    d.merge(i,j);
                    d.merge(i+n,j+n);
                }else swap(a[i][j],a[j][i]);
            }
        }
    }

    f(i, 1, n) f(j, 1, n) cout << a[i][j] << " \n"[j == n];
}