题解：P9841 [ICPC 2021 Nanjing R] Puzzle in Inazuma

· · 题解

以下是一大坨。

Part 1

首先可以令 G 上的边权全部减去 H 上对应边权。然后目标变成了把 G 上的权全部变成 0。

一个显然的想法是把 n,n-1,n-2,\dots,1 的邻边依次变为 0，当然这是做不到的。不过可以从 n 做到 5。

具体地，设当前枚举的点为 x，取出 1,2,3,4 放着作为工具点，对于 y>4，显然可以做一次 (x,1,2,y,-w_{x,y}) 操作把边 (x,y) 变成 0。

最后剩下 4 个点，怎么办？

给出第一个操作组：选定四个点 a,b,c,d，满足 w_{a,b} 为偶数，将 (a,b) 的权值全部转移至 (c,d)，不影响其余任何边。

操作：记初始 a,b 的边权为 w，进行 (c,a,b,d,\frac{w}{2}),(d,a,b,c,\frac{w}{2})。

可以画图发现这是对的。

所以如果 (x,i)（i=1,2,3,4）的边权是偶数，那么可以轻易地把它转移走。如果有奇数怎么办？

如果只看奇偶性的话，进行一次 (a,b,c,d,1) 实际上就是把六条边的边权的奇偶性都改变一次。对应到这个情境中，就是可以选择三个点，把 (x,a),(x,b),(x,c) 的边权奇偶性改变。

也就是：有 4 个取值 0/1 的数，每次把其中 3 个反转，要求全部变成 0。

无论如何都可以做到。下面不带编号地给出做法：

所以一定可以把 (x,1),(x,2),(x,3),(x,4) 的边权都变成偶数，最后再全部转移走即可。

Part 2

现在问题变成了一个 4 个点的完全图，首先可以手玩一下 n=4 何时有解。

首先边权和必定要为 0，因为操作不改变边权和。

其次，n=4 时只有 4 种本质不同的操作，即 a=1,2,3,4 时的操作，可以记操作的总权值为 x_1,x_2,x_3,x_4。则有方程：

x_1+x_2-x_3-x_4=-w_{1,2}\\ x_1-x_2+x_3-x_4=-w_{1,3}\\ x_1-x_2-x_3+x_4=-w_{1,4}\\ -x_1+x_2+x_3-x_4=-w_{2,3}\\ -x_1+x_2-x_3+x_4=-w_{2,4}\\ -x_1-x_2+x_3+x_4=-w_{3,4}\\ \end{cases}

所以可以得出结论：

w_{1,2}+w_{3,4}=w_{1,3}+w_{2,4}=w_{1,4}+w_{2,3}=0

这是另一个必要条件。

然后，进行加减消元，可以得出：

2(x_1-x_4)=-(w_{1,2}+w_{1,3}) 2(x_2-x_4)=-(w_{1,2}+w_{2,3}) 2(x_3-x_4)=-(w_{1,3}+w_{2,3})

所以右边三项都得是偶数，这是第三个必要条件。

都满足后，令 x_4=0，就可以得出 x_1,x_2,x_3，直接做就行。

Part 3

你要是认为这就做完了就大错特错了（这么认为的我就是大奶龙）。

以上只是 n=4 的情况，而非剩下 4 个点的情况。比方说，n=5 时，可以做到 n=4 做不到的操作。

我们已经知道了第一个操作组——对偶数边权的转移。所以给出结论：当且仅当剩下的 6 条边权奇偶性相同，且和为 0 时有解。

必要性证明略。充分性证明：如果权值都是奇数就先做一次 (1,2,3,4,1) 变成偶数。然后通过和 5 相邻的 4 条边，把所有边权转移到同一条边上即可。

Part 4

然而还没有完。n=5 时不能接受奇数边权，然而 n\ge 6 时是可以的。

给出第二个操作组：令 \{a,b,c,d\}=\{1,2,3,4\}，将 (a,d) 的边权减 1，(5,6) 的边权加 1，不影响其余任何边。

操作：先操作 (5,a,b,c,1),(d,b,c,5,1)，可以发现这样 (5,a),(5,d),(a,b),(a,c),(b,c),(c,d) 的边权分别增加 1；然后操作 (6,a,b,c,-1),(d,b,c,6,-1)，这样 (6,a),(6,d),(a,b),(a,c),(b,c),(c,d) 的边权分别减少 1，总体来看只有 (5,a),(5,d),(6,a),(6,d) 边权改变。最后操作 (6,5,a,d)，即可将 (5,6) 加 1，(a,d) 减 1，并将其余边权恢复。

画个图更容易理解。

所以，先判定边权和为 0，然后直接找出边权为奇数的边，把它们的边权转移 1 到 (5,6)，最后将 (5,6) 的边权（可以证明一定是个偶数）转移到某条边上，之后和 n=5 的一样。

总结

把 G 的边权减去 H，先把除 1,2,3,4 之间的边以外的边全部变成 0，然后分为 n=4、n=5 和 n\ge 6 分类讨论即可。

分析以下，除了一开始把其他边变成 0 花费了 O(n^2) 次操作外，剩余都是常数级别的，完全可以通过。实测本题数据每个点不超过 11000 次。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 105;

int G[maxn][maxn], H[maxn][maxn];
int ans[maxn * maxn * maxn][5], cnt = 0;

void operateG(int a, int b, int c, int d, int w){
    cnt ++, ans[cnt][0] = a, ans[cnt][1] = b, ans[cnt][2] = c, ans[cnt][3] = d, ans[cnt][4] = w;
    G[a][b] += w, G[b][a] += w, G[a][c] += w, G[c][a] += w, G[a][d] += w, G[d][a] += w;
    G[b][c] -= w, G[c][b] -= w, G[c][d] -= w, G[d][c] -= w, G[b][d] -= w, G[d][b] -= w;
}
void solve_even(){
    operateG(3, 1, 2, 4, G[1][2] / 2), operateG(4, 1, 2, 3, G[1][2]);
    operateG(4, 1, 2, 3, G[1][3] / 2), operateG(2, 1, 3, 4, G[1][3]);
    operateG(2, 1, 3, 4, G[1][4] / 2), operateG(3, 1, 2, 4, G[1][4]);

    operateG(1, 2, 3, 5, G[2][3] / 2), operateG(5, 1, 2, 3, G[2][3]);
    operateG(1, 3, 4, 5, G[3][4] / 2), operateG(5, 1, 3, 4, G[3][4]);
    operateG(2, 1, 4, 5, G[1][5] / 2), operateG(4, 1, 2, 5, G[1][5]);
}
void swap_one(int a, int b, int c, int d){
    operateG(5, a, b, c, 1), operateG(d, b, c, 5, 1);
    operateG(6, a, b, c, -1), operateG(d, b, c, 6, -1);
    operateG(6, 5, a, d, 1);
}

int main(){
    int n;
    scanf("%d", &n); 
    for(int i = 1; i <= n; i ++){
        for(int j = i + 1; j <= n; j ++){
            scanf("%d", &G[i][j]);
            G[j][i] = G[i][j];
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = i + 1; j <= n; j ++){
            scanf("%d", &H[i][j]);
            H[j][i] = H[i][j];
            G[i][j] -= H[i][j], G[j][i] -= H[j][i];
        }
    }
    for(int x = n; x >= 5; x --){
        for(int i = n; i >= 5; i --){
            if(i == x) continue;
            operateG(x, 1, 2, i, -G[x][i]);
        }
        int a = G[x][1] & 1, b = G[x][2] & 1, c = G[x][3] & 1, d = G[x][4] & 1;
        if(a + b + c + d == 4){
            operateG(x, 1, 2, 3, 1);
            operateG(x, 1, 2, 4, 1);
            operateG(x, 1, 3, 4, 1);
            operateG(x, 2, 3, 4, 1);
        }else if(a + b + c + d == 3){
            if(!a) operateG(x, 2, 3, 4, 1);
            else if(!b) operateG(x, 1, 3, 4, 1);
            else if(!c) operateG(x, 1, 2, 4, 1);
            else operateG(x, 1, 2, 3, 1);
        }else if(a + b + c + d == 2){
            if(a && b) operateG(x, 2, 3, 4, 1), operateG(x, 1, 3, 4, 1);
            else if(a && c) operateG(x, 2, 3, 4, 1), operateG(x, 1, 2, 4, 1);
            else if(a && d) operateG(x, 2, 3, 4, 1), operateG(x, 1, 2, 3, 1);
            else if(b && c) operateG(x, 1, 2, 4, 1), operateG(x, 1, 3, 4, 1);
            else if(b && d) operateG(x, 1, 2, 3, 1), operateG(x, 1, 3, 4, 1);
            else operateG(x, 1, 2, 3, 1), operateG(x, 1, 2, 4, 1);
        }else if(a + b + c + d == 1){
            if(a) operateG(x, 1, 2, 3, 1), operateG(x, 1, 2, 4, 1), operateG(x, 1, 3, 4, 1);
            else if(b) operateG(x, 1, 2, 3, 1), operateG(x, 1, 2, 4, 1), operateG(x, 2, 3, 4, 1);
            else if(c) operateG(x, 1, 2, 3, 1), operateG(x, 1, 3, 4, 1), operateG(x, 2, 3, 4, 1);
            else operateG(x, 1, 2, 4, 1), operateG(x, 1, 3, 4, 1), operateG(x, 2, 3, 4, 1);
        }
        a = -G[x][1] / 2, b = -G[x][2] / 2, c = -G[x][3] / 2, d = -G[x][4] / 2;
        operateG(x, 1, 2, 3, a), operateG(1, x, 2, 3, a);
        operateG(x, 2, 1, 3, b), operateG(2, x, 1, 3, b);
        operateG(x, 3, 1, 2, c), operateG(3, x, 1, 2, c);
        operateG(x, 4, 1, 2, d), operateG(4, x, 1, 2, d);
    }
    int w12 = -G[1][2], w13 = -G[1][3], w14 = -G[1][4], w23 = -G[2][3], w24 = -G[2][4], w34 = -G[3][4];
    if(n == 4){
        if(w12 + w34 != 0 || w13 + w24 != 0 || w14 + w23 != 0){
            printf("-1\n");
            return 0;
        }
        if(((w12 + w13) & 1) || ((w12 + w23) & 1) || ((w13 + w23) & 1)){
            printf("-1\n");
            return 0;
        }
        int x1 = (w12 + w13) / 2, x2 = (w12 + w23) / 2, x3 = (w13 + w23) / 2;
        operateG(1, 2, 3, 4, x1), operateG(2, 1, 3, 4, x2), operateG(3, 1, 2, 4, x3);
    }else if(n == 5){
        int sum = (w12 & 1) + (w13 & 1) + (w14 & 1) + (w23 & 1) + (w24 & 1) + (w34 & 1);
        if((sum != 0 && sum != 6) || (w12 + w13 + w14 + w23 + w24 + w34 != 0)){
            printf("-1\n");
            return 0;
        }
        if(sum == 6) operateG(1, 2, 3, 4, 1);
        solve_even();
    }else{
        if(w12 + w13 + w14 + w23 + w24 + w34 != 0){
            printf("-1\n");
            return 0;
        }
        if(G[1][2] & 1) swap_one(1, 3, 4, 2);
        if(G[1][3] & 1) swap_one(1, 2, 4, 3);
        if(G[1][4] & 1) swap_one(1, 2, 3, 4);
        if(G[2][3] & 1) swap_one(2, 1, 4, 3);
        if(G[2][4] & 1) swap_one(2, 1, 3, 4);
        if(G[3][4] & 1) swap_one(3, 1, 2, 4);
        operateG(1, 2, 5, 6, G[5][6] / 2), operateG(2, 1, 5, 6, G[5][6]);
        solve_even();
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i ++) printf("%d %d %d %d %d\n", ans[i][0], ans[i][1], ans[i][2], ans[i][3], ans[i][4]);
    return 0;
}