形式化题目

给定一张 $N$ 个顶点的无向图，顶点 $i$ 上有一个整数 $A_i$，且 $\sum_{i=0}^{N-1} A_i = 0$； 第 $j$ 条边 $(p_j, q_j)$ 带有代价 $T_j$。能量可以沿被选中的边任意流动， 一条边无论流过多少能量都只收 $T_j$ 一次。

要求选出一个边集 $E'$ 并决定各边上的流量，使每颗宝石的最终能量都相同， 求 $\sum_{e \in E'} T_e$ 的最小值；无法做到时输出 Impossible。

因为总和恒为 0，"所有能量相同"只能是全部为 0。所以目标等价于： 第 $i$ 颗宝石净流出 $A_i$（$A_i < 0$ 即净流入 $-A_i$）。

样例 1（$N = 3$，$A = [50, -20, -30]$）的图，顶点旁标注能量，边上标注代价：

1
2
3
4
5        0:+50
       /     \
     10      100
     /         \
 1:-20 --20-- 2:-30

顶点 0 富余 50，顶点 1、2 分别亏缺 20 和 30。取边 $(0,1)$（代价 10）与 $(1,2)$（代价 20）：顶点 0 沿 $(0,1)$ 送出 50，其中 20 留在顶点 1， 剩下的 30 沿 $(1,2)$ 转给顶点 2，总代价 $10 + 20 = 30$。那条代价 100 的边 $(0,2)$ 显然不划算。

正解

思路

朴素做法的瓶颈。 最直接的想法是枚举用哪些边：$E$ 有 $M$ 条边，枚举 $2^M$ 个边集， 逐个检查是否能让每颗宝石的需求被满足，取代价最小的那个。$M$ 最大 $N(N-1)/2 = 120$，$2^{120}$ 完全不可行。瓶颈在于枚举的是边，而"可行不可行" 这件事只取决于点被切成了哪几个连通块。

观察一：代价与流量无关，所以每个连通块里只需要一棵树。 既然一条边只收一次钱， 同一连通块里多留一条边不会让代价变低（非负权），而 $|S|$ 个点只需要 $|S| - 1$ 条边就能连通， 所以最优解中每个连通块都可取成一棵生成树，$|E'| \leqslant N - 1$。

观察二：边集可行 $\iff$ 它的每个连通分量内部 $\sum A_i = 0$。

• 必要性：能量只能沿 $E'$ 中的边流动，一个连通分量与外界没有通路，分量内的总能量守恒。 目标态要求分量内每颗宝石都是 0，即总量为 0，所以分量内初始总能量必须为 0。
• 充分性：设分量内总能量为 0。取这个分量的一棵生成树，从叶子开始自下而上处理： 叶子 $v$ 只有一条通向外面的树边，把它当前的差值沿这条边传给父节点， 然后删掉 $v$。每一步都保持"剩下的树上总需求仍为 0"，最后根节点的需求必然是 0。 整棵树每条边只传一次定量能量，所以这个边集确实可行。

这条判据把"流量怎么安排"整个问题消掉了：不需要考虑流量，只需要考虑点怎么分块。

观察三：给定块 $S$，块内最小代价就是 $S$ 的导出子图的最小生成树。 连通 $|S|$ 个点至少要 $|S| - 1$ 条边，而观察二的充分性构造说明任意一棵生成树都够用， 两边夹出这一结论。若 $S$ 的导出子图不连通，则 $S$ 无法单独成块，代价记为无穷大。

用 Kruskal 就能算出来：把全局的边按代价升序排好，只保留"两端都在 $S$ 内"的边， 直接在原序列上合并即可——不必为每个 $S$ 重新建图。

观察四：代价可加，所以可以按点集做划分 DP。 连通块之间互不影响， 总代价 = 各块代价之和。于是记 dp[S] 为"把点集 $S$ 划分成若干可独立调平的块"的最小代价， 枚举 $S$ 中含 $S$ 最低位的那一块 $T$ 来转移：

答案是 $dp[\,2^N - 1\,]$（全集对应的状态）。这里 $cost[T]$ 是观察三里的块内 MST。

为什么强制块含最低位？ 一份划分里"含最低位的那一块"是唯一的，强制带上它就等于给 每份划分指定了唯一的枚举顺序，同一个划分不会被按块的不同排列重复枚举；顺带还把内层 枚举量减半。

用小数据看这个 DP 怎么转。 自造一组 $N = 4$、$A = [3, -3, 5, -5]$ 的数据， 边只有 $(0,1)$ 代价 4、$(2,3)$ 代价 6、$(1,2)$ 代价 100：

1
2
3 块 A（能量和 0）:  {0:+3} --4-- {1:-3}
 块 B（能量和 0）:  {2:+5} --6-- {3:-5}
 跨块边（没人用）:  {1:-3} ---100--- {2:+5}

两个零和块各自连起来就完事了，那条 100 的边根本不需要选。 ok[sub] = total[sub] == 0 and cost[sub] < INF 是"这个点集能不能自己调平"，填表结果：

三列的含义：total 是子集能量和，只有它为 0 的集合才可能独立调平；cost 是该子集导出 子图上的 MST 代价（不连通或非零和都是 INF）；dp 是把子集划成若干合法块的最小总花费。 第一列是子集掩码的十进制值（第 $i$ 位为 1 表示点 $i$ 在集合里），枚举顺序与代码的 for sub in range(1, 1 << n) 一致。

最后一行的对比最值得看：整块连通要 110，而答案是 10。因为把 {0,1} 与 {2,3} 分开后 两块各自能量和为 0，可以自己调平，根本用不上那条 100 的跨组边。这直接说明不能偷懒去跑一次全图 MST——块内零和才是判据，全局连通不是必要条件。

实现对应。 solve() 先把边按代价升序排好，再用 lowbit 递推一次算出所有 total[sub] （去掉最低位再加回它，$O(2^N)$ 而不是每个子集重新求和）；cost 用列表推导对每个零和子集 调用一次 mst_weight；DP 用 block = (block - 1) & rest 枚举去掉最低位后的所有子集， low | block 就是含最低位的候选块。dp[sub] 的转移用到的是 sub 的真子集， 下标必然更小，所以正序循环就够，不需要记忆化递归。

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF = 1000000000000000000LL;

int n, m;
ll a[20];                // 各宝石能量
int eu[130], ev[130];    // 边的两端
ll ew[130];              // 边的代价

// total[sub]：sub 内所有宝石能量之和
ll total[1 << 16];
// cost[sub]：把 sub 内部连成一棵树的最小代价，连不通为 INF
ll cost[1 << 16];
char ok[1 << 16];        // sub 能否独立调平
ll dp[1 << 16];          // 拆成若干可独立调平的块的最小总花费

struct Edge { int u, v; ll w; };
Edge edges[130];

bool edge_cmp(const Edge& x, const Edge& y) { return x.w < y.w; }

// 只允许 sub 内的点参与，求其 MST 代价
ll mst_weight(int sub) {
    int parent[16];
    int vertices = 0;
    for (int i = 0; i < n; i++) {
        if ((sub >> i) & 1) { parent[i] = i; vertices++; }
    }
    // 朴素 find
    int merged = 0;
    ll weight = 0;
    for (int ei = 0; ei < m; ei++) {
        int u = edges[ei].u, v = edges[ei].v;
        if (!((sub >> u) & 1) || !((sub >> v) & 1)) continue;
        int ru = u; while (parent[ru] != ru) { parent[ru] = parent[parent[ru]]; ru = parent[ru]; }
        int rv = v; while (parent[rv] != rv) { parent[rv] = parent[parent[rv]]; rv = parent[rv]; }
        if (ru == rv) continue;
        parent[ru] = rv;
        merged++;
        weight += edges[ei].w;
        if (merged == vertices - 1) return weight;
    }
    return (merged == vertices - 1) ? weight : INF;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        eu[i] = edges[i].u; ev[i] = edges[i].v; ew[i] = edges[i].w;
    }
    // 按代价升序（Kruskal）
    sort(edges, edges + m, edge_cmp);

    int full = (1 << n) - 1;

    // total 打表：去掉最低位再加回
    total[0] = 0;
    for (int sub = 1; sub <= full; sub++) {
        int low = sub & (-sub);
        int idx = __builtin_ctz(low);
        total[sub] = total[sub ^ low] + a[idx];
    }

    // cost 打表
    cost[0] = 0;
    for (int sub = 1; sub <= full; sub++) {
        if (total[sub] == 0) cost[sub] = mst_weight(sub);
        else cost[sub] = INF;
    }

    // ok 判定
    for (int sub = 1; sub <= full; sub++)
        ok[sub] = (total[sub] == 0 && cost[sub] < INF);

    // dp：只枚举含 sub 最低位的块
    dp[0] = 0;
    for (int sub = 1; sub <= full; sub++) {
        int low = sub & (-sub);
        int rest = sub ^ low;
        ll best = INF;
        int block = rest;
        while (true) {
            int cand = low | block;
            if (ok[cand] && dp[sub ^ cand] < INF) {
                ll v = dp[sub ^ cand] + cost[cand];
                if (v < best) best = v;
            }
            if (block == 0) break;
            block = (block - 1) & rest;
        }
        dp[sub] = best;
    }

    if (dp[full] < INF) cout << dp[full] << "\n";
    else cout << "Impossible\n";
    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85#!/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-02 02:11
# update_at: 2026-10-02 02:17

import sys

INF = 10 ** 18  # 远超任何可行总花费：MST 最多约 15*1000，分组总和只会更小


def mst_weight(sub: int, edges: list[tuple[int, int, int]]) -> int:
    """只允许 sub 内的宝石参与时，把它们连成一体的最小花费；连不通返回 INF。

    Kruskal：edges 已按代价升序，两端都落在 sub 内的边才可用。并到"点数 - 1 条边"
    就提前收工，稠密图上不必白扫剩余边。
    """
    vertices = sub.bit_count()
    # 只给 sub 里的点建并查集：range(sub.bit_length()) 恰好覆盖 sub 可能出现的所有位
    parent = {i: i for i in range(sub.bit_length()) if sub >> i & 1}

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]                # 路径压缩，顺手改写成迭代
            x = parent[x]
        return x

    merged = weight = 0
    for u, v, t in edges:
        if not (sub >> u & 1 and sub >> v & 1):
            continue                                     # 有端点不在 sub 内，这条边用不上
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        parent[ru] = rv
        merged += 1
        weight += t
        if merged == vertices - 1:
            return weight                                # n-1 条边到齐，已经是一棵树
    return weight if merged == vertices - 1 else INF     # 没并满 = 这个点集本身不连通


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    a = [next(data) for _ in range(n)]
    edges = sorted([(next(data), next(data), next(data)) for _ in range(m)], key=lambda e: e[2])
    full = (1 << n) - 1

    # total[sub]：sub 里所有宝石的能量之和。去掉最低位再加回它，一次 O(2^n) 打表。
    total = [0] * (1 << n)
    for sub in range(1, 1 << n):
        low = sub & -sub
        total[sub] = total[sub ^ low] + a[low.bit_length() - 1]

    # cost[sub]：只调平 sub 内部所需的最小花费。总能量不为 0 的集合永远调不平，代价记 INF。
    cost = [0] + [mst_weight(sub, edges) if total[sub] == 0 else INF
                  for sub in range(1, 1 << n)]

    # ok[sub]：sub 能否"独立调平"——总能量为 0（进出的能量相等）且内部连通（能量传得动）。
    ok = bytearray(1 << n)
    for sub in range(1, 1 << n):
        ok[sub] = total[sub] == 0 and cost[sub] < INF

    # dp[sub]：把 sub 拆成若干个可独立调平的块的最小总花费。只枚举含 sub 最低位的块，
    # 因为每一份拆法里含最低位的块唯一，这样同一份拆法不会换着顺序被重复枚举。
    dp = [0] + [INF] * full
    for sub in range(1, 1 << n):
        low = sub & -sub
        rest = sub ^ low
        block, best = rest, INF
        while True:
            cand = low | block                               # 候选块：sub 中含最低位的子集
            if ok[cand]:
                best = min(best, dp[sub ^ cand] + cost[cand])
            if block == 0:
                break
            block = (block - 1) & rest                       # 枚举 rest 的所有子集
        dp[sub] = best
    print(dp[full] if dp[full] < INF else "Impossible")


if __name__ == "__main__":
    solve()

复杂度

• 时间：子集能量和 $O(2^N)$，每个零和子集求一次 MST 共 $O(2^N M)$， 划分 DP 枚举"含最低位的子集"，总量为 $\sum_{S \neq \varnothing} 2^{|S|-1} = (3^N - 1)/2$， 即 $O(3^N)$。总复杂度 $O(2^N M + 3^N)$，$N = 16$ 时约 $2.15 \times 10^7$ 次转移。
• 空间：total、cost、dp 三个长度 $2^N$ 的数组，加 ok 的 $2^N$ 字节和边表 $O(M)$，共 $O(2^N + M)$。$N = 16$ 时实测峰值内存约 19 MB。

总结

• 本题的关键不在图论技巧，而在换一个枚举对象：从"枚举边集"（$2^M$）换成 “枚举点集的划分”（$3^N$）。$N \leqslant 16$ 的提示就在这里。
• 换过去的依据是观察一、二：一条边只收一次钱 ⇒ 每个连通块是一棵树； 能量出不了连通块 ⇒ 块内能量和必须为 0。这两条把"流量安排"整个消掉， 可行性变成一条只与点集有关的判据。
• 判据立住之后，块内最优代价就是子集 MST，块与块之间代价可加， 于是只需一个划分 DP 把它们拼起来。
• 两个容易踩的坑：不要直接跑全图 MST（块内零和才是判据，见上面那个 cost = 110 / dp = 10 的例子）；DP 转移要固定"含最低位的那块"， 否则同一份划分会被反复枚举。
• 全部 $A_i$ 为 0 时答案是 0（每个单点自己就是零和块）。无解有明确的判据： 块必须整个落在全图的一个连通分量里，所以只要某个连通分量的能量和不为 0， 它内部的块之和就不可能全为 0，答案一定是 Impossible；反之若每个连通分量都零和， 直接按连通分量分块即可（因此在全图连通时必然有解）。

图示解析

这张图把从题意到答案的整条路线串起来：

1
2
3
4
5
6
7N 颗宝石 + 能量 A + 带权边
`- 一条边只收一次钱  ->  最优解每个连通块都是一棵树
   `- 能量出不了连通块  ->  合法块 <=> 块内 sum A = 0
      `- 块内最小代价   ->  该点集导出子图的 MST   (Kruskal 过滤边)
         `- 块与块代价可加  ->  子集划分 DP
            `- dp[S] = min(cost[T] + dp[S \ T]),  T 含 lowbit(S)
               `- 答案 dp[2^n - 1], 无解则 Impossible

沿着箭头看：前两步是建模（把"流量"消成"点集划分"），中间两步是预处理 （total 与 cost 两张表），最后一步是合并（划分 DP）。每一步都只用到上一步的结论， 中间任何一步换掉都会让复杂度升一个量级——比如跳过"块内零和"直接跑全图 MST， 得到的就会是上面那个例子里 cost = 110，而不是正确答案 dp = 10。