一、题意简述

• 有 $n$ 个点（岛屿），$m$ 条无向边（可能自环、重边）。
• 图分成若干个连通块（区域）。
• 一个区域是幸运的，当且仅当它包含的岛屿数量是一个幸运数字（十进制只含 $4$ 和 $7$，例如 $4,7,44,47,74,77$ 等）。
• 初始可能没有幸运区域。
• 可以在不同区域之间加边，从而把多个区域合并成一个新区域。
• 问：最少加多少条边，能让图中存在至少一个幸运区域？
  若无解，输出 $-1$。

---

二、问题转化（图论 → 背包）

1. 连通块是基本单元
   设第 $i$ 个连通块的大小为 $s_i$（点数）。 在合并过程中，我们只关心这些 $s_i$，不关心具体内部结构。

2. 合并的代价
   如果我们选择 $k$ 个连通块（大小分别为 $s_{i_1}, s_{i_2}, \dots, s_{i_k}$），
   将它们合并成一个区域需要添加 $k-1$ 条边（因为 $k$ 个连通块连通成 $1$ 个需要 $k-1$ 条路）。

3. 条件
   合并后的总大小：

   $$S = s_{i_1} + s_{i_2} + \dots + s_{i_k}$$

   必须是一个幸运数字。

4. 目标
   最小化 $k-1$，即最小化 $k$（选中的连通块个数）。

---

三、重新表述为“多重背包”

变量定义

• 设共有 $p$ 个连通块。
• 对于每个可能的大小 $x$，记 $c_x$ 表示大小为 $x$ 的连通块的个数。
• 显然：$$\sum_{x} c_x \cdot x = n$$

背包模型

• 每个连通块是一个物品：
  • 重量 $w = x$
  • 价值 $v = 1$（表示该块被选中）
• 每个物品最多用一次。
• 目标：对于每个幸运数字 $L$，能否恰好凑出总重量 $L$，并且使选中物品个数最少？
• 最后答案：$$\min_{L \text{ 幸运}} (\text{最少需要} L \text{的物品数} - 1) $$

---

四、DP 状态与转移

设：

$$dp[t] = \text{凑出总大小 } t \text{ 所需的最少连通块个数}$$

初始化：

$$dp[0] = 0,\quad dp[t] = +\infty\ (t>0)$$

对于每一种大小 $x$，有 $c_x$ 个这样的连通块。
这是一个多重背包，可以用二进制拆分优化：

二进制拆分

将 $c_x$ 拆成：

$$1,\ 2,\ 4,\ \dots,\ 2^k,\ r\ \ (r < 2^{k+1})$$

每个拆分出来的数量 $m$ 对应一个组合物品：

• 重量 = $m \cdot x$
• 价值 = $m$（选了多少个块）

然后用 0/1 背包处理这些组合物品，转移：

$$dp[t] = \min(dp[t],\ dp[t - m \cdot x] + m)$$

必须倒序循环 $t$。

---

五、为什么不同 $x$ 的个数是 $O(\sqrt{n})$？

• 不同的大小 $x$ 互不相同。
• 每个 $x$ 至少出现 1 次。
• 设不同大小的个数为 $k$，则：$$n = \sum c_x \cdot x \ge \sum x \ge 1 + 2 + \dots + k = \frac{k(k+1)}{2} $$因此：$$k = O(\sqrt{n})$$

所以总复杂度：

• 二进制拆分后总物品数 $O(\sqrt{n} \log n)$
• 背包容量 $O(n)$
• 总时间复杂度 $O(n \sqrt{n} \log n)$，在 $n \le 10^5$ 时可接受。

---

六、最终答案

$$\text{ans} = \min_{\substack{L \le n \\ L \text{ 幸运}}} \big( dp[L] - 1 \big) $$

如果所有幸运 $L$ 的 $dp[L] = +\infty$，输出 $-1$。

---

七、标程

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct DSU {
    vector<int> parent, sz;
    DSU(int n) {
        parent.resize(n);
        sz.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
    }
    int get_size(int x) {
        return sz[find(x)];
    }
};

bool is_lucky(int x) {
    if (x == 0) return false;
    while (x > 0) {
        int d = x % 10;
        if (d != 4 && d != 7) return false;
        x /= 10;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        dsu.unite(u, v);
    }

    // 统计每个连通块的大小
    vector<int> comp;
    vector<bool> vis(n, false);
    for (int i = 0; i < n; i++) {
        int r = dsu.find(i);
        if (!vis[r]) {
            vis[r] = true;
            comp.push_back(dsu.get_size(i));
        }
    }

    // 压缩成 (size, count)
    map<int, int> mp;
    for (int x : comp) mp[x]++;

    // 多重背包
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    for (auto& [x, cnt] : mp) {
        // 二进制拆分
        for (int k = 1; cnt > 0; k <<= 1) {
            int take = min(k, cnt);
            int w = take * x;
            int val = take;
            for (int t = n; t >= w; t--) {
                if (dp[t - w] != INF) {
                    dp[t] = min(dp[t], dp[t - w] + val);
                }
            }
            cnt -= take;
        }
    }

    int ans = INF;
    for (int L = 1; L <= n; L++) {
        if (is_lucky(L) && dp[L] != INF) {
            ans = min(ans, dp[L] - 1);
        }
    }

    if (ans == INF) ans = -1;
    cout << ans << '\n';

    return 0;
}

---

八、示例验证

示例 1

4 3
1 2
2 3
1 3

• 连通块：大小 $3$、大小 $1$
• 背包：$3$ 和 $1$
• 幸运数字 $4$：可以用 $3+1$，需要 $2$ 个块 → 加 $1$ 条路
  输出 $1$ ✅

示例 2

5 4
1 2
3 4
4 5
3 5

• 连通块：大小 $2$、大小 $3$
• 可凑出的总大小：$2,3,5$
• 幸运数字 $\le 5$：$4$ 无法凑出
  输出 $-1$ ✅

---