最小花费

GitHub跳转原题关系图返回列表

询问 [i,j] 的奇偶性等于前缀异或 S_{i-1} xor S_j,定出全部 x_i 等价于把 n+1 个前缀点连通,答案是该完全图的最小生成树。

OJ: roj

题目 ID: 1711

难度:提高

标签:最小生成树图论primpython

创建: 2026-10-07 18:05

更新: 2026-10-07 18:05

形式化题目

有 nn 个未知的 0/10/1 变量 x1,x2,…,xnx_1, x_2, \dots, x_n。一次询问给定区间 [i,j][i,j], 返回 xi⊕xi+1⊕⋯⊕xjx_i \oplus x_{i+1} \oplus \cdots \oplus x_j(即该区间和的奇偶性),代价为 c[i,j]c[i,j]。 要求选出一组询问,使得由这组询问的答案能够唯一确定 x1,…,xnx_1, \dots, x_n, 并让总代价最小。求最小总代价。

形式化地:把每个区间 [i,j][i,j] 看成一条无向边 (i−1, j)(i-1,\,j)、权为 c[i,j]c[i,j], 作用在点集 {0,1,…,n}\{0, 1, \dots, n\} 上。选边集 E′E',使每个点 i∈[1,n]i \in [1,n] 都能通过 E′E' 中的路径与点 00 相连,最小化 ∑e∈E′we\sum_{e \in E'} w_e。

正解

思路

第一步:把"区间和"换成"前缀异或"。 令前缀异或

S0=0,Sk=x1⊕x2⊕⋯⊕xk(1⩽k⩽n).S_0 = 0, \qquad S_k = x_1 \oplus x_2 \oplus \cdots \oplus x_k \quad (1 \leqslant k \leqslant n).

由于 ⊕\oplus 是模 22 加法,区间异或就是两个前缀异或的差:

xi⊕⋯⊕xj=Sj⊕Si−1.x_i \oplus \cdots \oplus x_j = S_j \oplus S_{i-1}.

于是一次询问 [i,j][i,j] 给出的是 Si−1S_{i-1} 与 SjS_j 之间的异或关系, 而且 xk=Sk−1⊕Skx_k = S_{k-1} \oplus S_k:只要所有 SkS_k 都确定了,所有 xkx_k 就都确定了; 反过来,某个 SkS_k 定不下来,xkx_k 和 xk+1x_{k+1} 就都有两种可能。 所以目标等价于:让每一个 SkS_k 都被唯一确定。

第二步:哪些 SkS_k 能被确定? 已知 S0=0S_0 = 0。把询问看成图上的边: 询问 [i,j][i,j] 在点 i−1i-1 与点 jj 之间连一条边。若 kk 与 00 在同一个连通块里, 沿路径把边上的异或关系乘起来,就能算出 Sk⊕S0=SkS_k \oplus S_0 = S_k,即 SkS_k 被确定; 若 kk 与 00 不连通,那么把这一块的 SS 值整体同时异或 11, 所有询问答案都不变(每条边两端同时翻转,异或值不变),而 SkS_k 变了, 说明 SkS_k 无法确定。因此

一组询问能确定全部 xix_i   ⟺  \iff 图 (V={0,…,n}, E′)(V=\{0,\dots,n\},\,E') 中每个点都与点 00 连通。

第三步:连通的最小代价 = 最小生成树。 要求 E′E' 让 n+1n+1 个点连通, 即 E′E' 含一棵生成树,∑e∈E′we⩾\sum_{e \in E'} w_e \geqslant 该图的最小生成树权; 而任意一棵生成树本身就让所有点连通、就是一组合法方案。 两边夹逼,答案恰为

MST(Kn+1,  w(a,b)=c[a+1][b]  (a<b)).\text{MST}\Bigl(K_{n+1},\; w(a,b) = c[a+1][b]\ \ (a < b)\Bigr).

第四步:为什么用朴素 Prim。 边数是 Θ(n2)\Theta(n^2),n⩽2000n \leqslant 2000 时约 2×1062 \times 10^6 条边。 稠密图上 Prim 每次 O(n)O(n) 找最近点、O(n)O(n) 松弛,总复杂度 O(n2)O(n^2), 不需要堆,也不需要把边排出来(Kruskal 反而要 O(n2log⁡n)O(n^2 \log n) 排序)。

以样例为例,n=3n = 3,题面给的三行是 c[1,1..3]=1,2,3c[1,1..3] = 1,2,3、c[2,2..3]=2,2c[2,2..3] = 2,2、c[3,3]=1c[3,3] = 1,对应 6 条边:

询问 边 权
[1,1][1,1] (0,1)(0,1) 1
[1,2][1,2] (0,2)(0,2) 2
[1,3][1,3] (0,3)(0,3) 3
[2,2][2,2] (1,2)(1,2) 2
[2,3][2,3] (1,3)(1,3) 2
[3,3][3,3] (2,3)(2,3) 1
graph LR
  0 -- 1 --- 1
  2 -- 2 --- 0
  3 -- 3 --- 0
  1 -- 2 --- 2
  1 -- 2 --- 3
  2 -- 1 --- 3

取边 (0,1)(0,1)(1)、(2,3)(2,3)(1)、(0,2)(0,2)(2),三个点 1,2,31,2,3 都与 00 连通, 总代价 1+1+2=41+1+2 = 4,与样例输出一致。这三条边确实够用:S1S_1 由 [1,1][1,1] 直接得到, S3S_3 由 [3,3][3,3] 得到,S2S_2 由 [1,2][1,2] 得到,四个前缀全定,x1..x3x_1..x_3 自然全定。

易错点。

  • 答案是 nn 条边(生成树)的权之和,最大为 n×109=2×1012n \times 10^9 = 2 \times 10^{12}, 必须用 64 位整数。
  • 边权可以为 00,此时"不询问"和"询问"代价相同,生成树照常可以取零权边, 算法不需要为 00 做任何特判;全零数据答案为 00。
  • 点集是 n+1n+1 个(S0S_0 也算一个点),只连 nn 个点会漏掉 x1x_1 或 xnx_n 的信息。

代码

Python 版(用 array 存平铺矩阵,Prim 的松弛走切片,避免 O(n2)O(n^2) 的 Python 级内层循环):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:46
# update_at: 2026-10-07 18:05

import sys
from array import array
from collections.abc import Iterator
from itertools import islice

BIG = 2 * 10**9  # 哨兵:比单条费用的上限 10^9 大,且放得进 int32;本题是完全图,不会真的取到

type Weights = array  # 平铺的 (n+1)×(n+1) 对称邻接矩阵,w[a*V+b] 是边 (a,b) 的权


def build_weights(n: int, data: Iterator[int]) -> Weights:
    """把输入的三角形费用摊成对称邻接矩阵:边 (a,b)(a<b)的权是题面的 c[a+1][b]。"""
    V = n + 1
    w = array('i', [BIG]) * (V * V)  # 单条费用 <= 10^9,int32 够用,矩阵只要 16 MB
    for i in range(1, n + 1):
        row_len = n + 1 - i                         # 题面第 i 行有 n+1-i 个费用
        row = array('i', islice(data, row_len))
        w[(i - 1) * V + i:i * V] = row              # 上三角:w[i-1][j] = c[i][j]
        start = i * V + i - 1                       # 下三角 w[j][i-1](j ≥ i)的首个下标
        w[start:start + len(row) * V:V] = row       # 按列步长 V 写入,保持矩阵对称
    return w


def mst(w: Weights, V: int) -> int:
    """完全图上跑朴素 Prim:每轮取未入树的最近点,并用切片整体松弛,返回总权。"""
    dist = [BIG] * V          # dist[u] = 未入树的点 u 到当前树的最小边权
    dist[0] = 0               # 点 0 是前缀和 S_0 = 0,从它出发
    unused = list(range(V))
    total = 0
    for _ in range(V):
        v = min(unused, key=dist.__getitem__)       # 未入树的最近点
        unused.remove(v)
        total += dist[v]
        dist[:v] = map(min, dist[:v], w[v::V])                          # u < v:矩阵第 v 列
        dist[v + 1:] = map(min, dist[v + 1:], w[v * V + v + 1:(v + 1) * V])  # u > v:第 v 行
    return total


def solve() -> None:
    # 先把 2·10^6 个整数压进 array:这样分词产生的字节对象能立刻释放,
    # 否则它们会和 16 MB 的矩阵同时驻留,峰值内存多出约 110 MB。
    nums = array('i', map(int, sys.stdin.buffer.read().split()))
    n = nums[0]
    print(mst(build_weights(n, islice(nums, 1, None)), n + 1))


if __name__ == "__main__":
    solve()

C++ 版(同一算法,朴素 Prim):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 17:46
 * update_at: 2026-10-07 18:05
 */
// 最小花费:询问区间 [i,j] 的和的奇偶性 = 前缀异或 S_{i-1} xor S_j,
// 要把每个 x_i 定下来,就必须把全部前缀点 S_0..S_n 连成一块(S_0 = 0 已知),
// 于是答案就是 n+1 个点、边 (i-1,j) 权为 c[i,j] 的完全图的最小生成树。
// 稠密图用朴素 Prim,O(n^2)。
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 2005;   // n 的上限 2000,点数 V = n+1 <= 2001
const ll INF = 4000000000000000000LL; // 4×10^18,比最大可能答案(2000 * 10^9)大得多

int V;                   // 点数 = n+1,前缀点为 0..n
int w[MAXN * MAXN];      // 平铺的对称邻接矩阵,w[a*V+b] = 边 (a,b) 的权,a<b 时为 c[a+1][b]
ll minDist[MAXN];        // minDist[u] = 未入树的点 u 到当前生成树的最小边权
char used[MAXN];         // used[u] = 点 u 是否已进入生成树

// fread 缓冲的快速读入:最大输入约 22MB,逐个 scanf 会超时
static char buf[1 << 16];
static size_t bufLen = 0, bufPos = 0;

// 取下一位字符,缓冲空了就补一次
static inline int nextChar() {
    if (bufPos == bufLen) {
        bufLen = fread(buf, 1, sizeof(buf), stdin);
        bufPos = 0;
        if (bufLen == 0) return -1;
    }
    return buf[bufPos++];
}

// 读一个非负整数(本题费用 0 <= c <= 10^9,用 int 就够)
int readInt() {
    int c = nextChar();
    while (c != -1 && (c < '0' || c > '9')) c = nextChar();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = nextChar();
    }
    return x;
}

int main() {
    int n = readInt();
    V = n + 1;
    // 题面第 i 行给的是 c[i][j] (i <= j <= n),它正是前缀点 i-1 与 j 之间的边权
    for (int i = 1; i <= n; ++i) {
        int a = i - 1;
        for (int j = i; j <= n; ++j) {
            int cost = readInt();
            w[a * V + j] = cost; // 上三角
            w[j * V + a] = cost; // 对称的下三角
        }
    }

    for (int u = 0; u < V; ++u) {
        minDist[u] = INF;
        used[u] = 0;
    }
    minDist[0] = 0; // 从点 0 出发

    ll ans = 0;
    for (int step = 0; step < V; ++step) {
        int v = -1; // 未入树点中离树最近的那个
        for (int u = 0; u < V; ++u)
            if (!used[u] && (v == -1 || minDist[u] < minDist[v])) v = u;
        used[v] = 1;
        ans += minDist[v];
        // 用新入树的 v 松弛其余未入树点
        for (int u = 0; u < V; ++u)
            if (!used[u] && w[v * V + u] < minDist[u]) minDist[u] = w[v * V + u];
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

  • 时间:建图读入 Θ(n2)\Theta(n^2);朴素 Prim 是 n+1n+1 轮,每轮 O(n)O(n) 找点、O(n)O(n) 松弛, 共 O(n2)=4×106O(n^2) = 4 \times 10^6 次基本操作。
  • 空间:平铺的对称邻接矩阵 (n+1)2(n+1)^2 个整数, C++ 用 int 约 16 MB(10910^9 放得下 int),Python 用 array('q') 约 32 MB; 其余辅助数组 O(n)O(n)。
  • Python 侧风险:C++ 限时 1000 ms,纯 Python 的 O(n2)O(n^2) 常数偏大, n=2000n = 2000 时本解法实测约 2 s(松弛已压到切片 + min 的 C 层,只剩找最近点是 O(n)O(n) 的 C 层扫描),可能 TLE;但算法与 C++ 同阶,没有降级成暴力。 读入用 sys.stdin.buffer.read().split() 一次性分词,峰值内存约 150 MB, 在 256 MB 限制内。

总结

  • 区间异或 → 前缀异或 → 图上一条边:这是本题唯一的建模步骤, Sj⊕Si−1S_j \oplus S_{i-1} 与边 (i−1,j)(i-1, j) 的对应关系是整个解法的支点。
  • “能确定”= “连通”:充分性靠沿路径累乘异或,必要性靠"连通块整体异或 1"的对称性论证; 这一步把信息论问题翻译成纯图论问题。
  • 最小连通 = 最小生成树:任何连通子图含生成树,任何生成树都连通,两边夹逼即答案。
  • 稠密图选 Prim:2×1062 \times 10^6 条边不值得排出来,O(n2)O(n^2) 的朴素 Prim 最省事, 也正好用"一维平铺矩阵 + 对称填表"避开三角形的下标换算。

数据说明

本题素材源目录里带有数据生成脚本 data.py,其建模与上文一致 (n+1 个点的完全图最小生成树,边 (i−1,j)(i-1,j) 权 c[i,j]c[i,j]),10 个测试点覆盖 n=3,5,10,50,200,500,1000,1500,2000n = 3,5,10,50,200,500,1000,1500,2000、全零边权、全 10910^9 边权等情形。 因此题面是重建的、并非官方原始数据,出题意图以 data.py 的建模为准; std.cpp 与本解法的建模一致(已用真实 data/ 逐点核对输出)。