自动搬运

查看原文

来自洛谷，原作者为

	modfish_ 你指尖跃动的电光，事静电罢（恼

搬运于2025-08-24 22:52:20，当前版本为作者最后更新于2025-07-08 18:57:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

以下是一大坨。

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$。

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

• $4$ 个 $1$：$\{1,1,1,1\}\rightarrow\{1,0,0,0\}\rightarrow\{0,1,1,0\}\rightarrow\{1,0,1,1\}\rightarrow\{0,0,0,0\}$。
• $3$ 个 $1$：$\{1,1,1,0\}\rightarrow\{0,0,0,0\}$。
• $2$ 个 $1$：$\{1,1,0,0\}\rightarrow\{1,0,1,1\}\rightarrow\{0,0,0,0\}$。
• $1$ 个 $1$：$\{1,0,0,0\}\rightarrow\{0,1,1,0\}\rightarrow\{1,0,1,1\}\rightarrow\{0,0,0,0\}$。
• $0$ 个 $1$：不用操作。

所以一定可以把 $(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$。则有方程：

$$\begin{cases} 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;
}