1or2 - 题解

标签与难度

标签: 网络流, 最大流, Dinic算法, 图论, 建模, 二分图匹配, 构造难度: 2100

题目大意喵~

主人，你好呀~！这道题是这样的：我们有一个 n 个点 m 条边的无向图。对于每个点 i，都有一个目标度数 d_i，这个值要么是1，要么是2。

我们的任务是，判断一下，能不能从原来的 m 条边里，挑选出一个边的子集，组成一个新的图。在这个新图里，每个点 i 的度数（就是连接到它的边的数量）要正好等于 d_i 呐。

如果可以做到，就输出 "Yes"；如果不行，就输出 "No"，喵~

解题思路分析

这道题看起来是在问我们“能不能选”，这种决策性的问题，很多时候都可以转化成更经典的算法模型来解决哦，喵~ 看到这种“每个点有需求”、“每条边有贡献”的设定，我的直觉告诉我，这很可能是一个网络流问题！

让我们一步步来分析怎么把这个问题变成一个最大流模型吧！

Step 1: 初始的思考和约束

首先，我们来想一些最基本的限制。在一个图里，所有顶点的度数之和一定等于边数的两倍，所以度数之和必然是偶数。那么，如果我们被要求的总度数 Σd_i 是个奇数，那肯定是无论如何都凑不出来的啦。所以，这是一个无解的必要条件。

\text{如果 } \sum_{i=1}^{N} d_i \text{ 是奇数，直接输出 "No" 就好啦！}

Step 2: 核心思想——流量分配

我们可以把“满足度数限制”看作是一个资源分配的过程。

每个顶点 i 需要 d_i 个“度数单位”。
每一条被选中的边 (u, v) 会给顶点 u 和顶点 v 各提供 1 个“度数单位”。

我们的目标就是，看看能不能通过选择边，完美地满足所有顶点的“度数单位”需求。这不就是网络流最擅长解决的匹配和分配问题嘛？

Step 3: 构建网络流模型

既然想用网络流，我们就要建一张有向图，包含源点 S 和汇点 T。

这个模型非常经典和巧妙，主人可要看仔细咯~

创造节点
- 一个源点 S 和一个汇点 T。
- 对于原图中的每一个顶点 i (从 1 到 N)，我们都在网络流图中创建两个对应的节点：一个叫 U_i（可以想成出度节点），另一个叫 V_i（可以想成入度节点）。
连接边，设定容量
- 源点到出度节点: 从源点 S 向每一个 U_i 节点连接一条有向边，容量为 d_i。
  - S -> U_i，容量为 d_i。
  - 含义: 这代表顶点 i 最多可以“提供” d_i 个度数。这就像是给每个顶点 i 发放了 d_i 张“度数券”。
- 入度节点到汇点: 从每一个 V_i 节点向汇点 T 连接一条有向边，容量也为 d_i。
  - V_i -> T，容量为 d_i。
  - 含义: 这代表顶点 i 必须“消耗” d_i 个度数。这就像是每个顶点 i 有 d_i 个“度数任务”需要完成。
- 中间的连接: 对于原图中的每一条边 (a, b)，我们在网络流图中创建两条有向边，容量都为 1。
  - U_a -> V_b，容量为 1。
  - U_b -> V_a，容量为 1。
  - 含义: 这两条边代表了原图中的无向边 (a, b)。如果有一单位的流量从 U_a 流向 V_b，就意味着我们选择了边 (a, b)，并且它为 a 提供了一个出度，为 b 提供了一个入度。反之，流量从 U_b 流向 V_a 也是一样的效果。容量为1保证了同一条边最多被选择一次。

示意图大概是这个样子哒： Network Flow Model

Step 4: 求解与判断

模型建好啦！现在我们来想一想，如果存在一个合法的选边方案，会对应网络流图里的什么情况呢？

如果存在一个方案，那么：

每个顶点 i 都恰好有 d_i 条边被选中。
在我们的模型里，这意味着从 S 出发的 d_i 容量会被全部用完，流向对应的 U_i。
同时，流入 T 的 d_i 容量也需要被全部填满，这些流量来自于对应的 V_i。
中间的流量完美地通过 U_a -> V_b 这样的边进行传输，每一次传输都代表一条边的选择。

所以，我们需要满足的总流量需求是所有 d_i 的和，即 Σd_i。

我们只需要在这个网络上跑一遍最大流算法（比如高效的 Dinic 算法），计算从 S 到 T 的最大流量 max_flow。

如果 max_flow 等于 Σd_i，说明所有顶点的度数需求都被完美满足了！就像所有的“度数券”都找到了对应的“度数任务”，喵~ 这时答案就是 "Yes"。
如果 max_flow 小于 Σd_i，说明无论如何调整，总有顶点的度数需求无法被满足。这时答案就是 "No"。

总结一下，解题步骤就是：

读取 N, M 和所有 d_i。
计算总度数需求 total_d = Σd_i。如果 total_d 是奇数，直接输出 "No"。
根据上面的规则构建网络流图。
用 Dinic 算法求出 S到T的最大流 max_flow。
比较 max_flow 和 total_d，如果相等则输出 "Yes"，否则输出 "No"。

是不是很奇妙呢？我们把一个图的构造问题，变成了一个流量是否能跑满的问题，喵~

代码实现

这是我根据上面的思路，为你精心重构的一份代码~ 注释很详细，希望能帮到你哟！

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// 网络流中的边
struct Edge {
    int to;         // 这条边的终点
    long long capacity; // 边的容量
    int rev;        // 反向边的索引，方便快速查找
};

// 用于Dinic算法的图结构
vector<vector<Edge>> adj; // 邻接表
vector<int> level;        // 节点层数，用于BFS分层
vector<int> iter;         // 当前弧优化，记录每个节点当前遍历到的边

// 添加一条从 from 到 to，容量为 cap 的边
void add_edge(int from, int to, long long cap) {
    adj[from].push_back({to, cap, (int)adj[to].size()});
    adj[to].push_back({from, 0, (int)adj[from].size() - 1}); // 同时添加反向边，初始容量为0
}

// BFS 用于在残差网络上构建分层图
bool bfs(int s, int t) {
    level.assign(adj.size(), -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (const auto& edge : adj[v]) {
            if (edge.capacity > 0 && level[edge.to] < 0) {
                level[edge.to] = level[v] + 1;
                q.push(edge.to);
            }
        }
    }
    return level[t] != -1; // 如果汇点T可达，说明找到了增广路
}

// DFS 用于在分层图上寻找增广路并更新流量
long long dfs(int v, int t, long long f) {
    if (v == t) return f;
    for (int& i = iter[v]; i < adj[v].size(); ++i) {
        Edge& e = adj[v][i];
        if (e.capacity > 0 && level[v] < level[e.to]) {
            long long d = dfs(e.to, t, min(f, e.capacity));
            if (d > 0) {
                e.capacity -= d;
                adj[e.to][e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

// Dinic算法主函数
long long max_flow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
        iter.assign(adj.size(), 0);
        long long f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

void solve() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> d(n + 1);
        long long total_d = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> d[i];
            total_d += d[i];
        }

        if (total_d % 2 != 0) {
            cout << "No" << endl;
            // 读取完本组测试数据的剩余部分
            for (int i = 0; i < m; ++i) {
                int u, v;
                cin >> u >> v;
            }
            continue;
        }

        // --- 网络构建 ---
        // 节点编号:
        // 0: 源点 S
        // 1 to n: U_i 节点 (出度节点)
        // n+1 to 2n: V_i 节点 (入度节点)
        // 2n+1: 汇点 T
        int s = 0, t = 2 * n + 1;
        int num_nodes = 2 * n + 2;
        adj.assign(num_nodes, vector<Edge>());

        // 1. S -> U_i
        for (int i = 1; i <= n; ++i) {
            add_edge(s, i, d[i]);
        }

        // 2. V_i -> T
        for (int i = 1; i <= n; ++i) {
            add_edge(n + i, t, d[i]);
        }
        
        // 3. U_a -> V_b 和 U_b -> V_a
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            // 容量为1，代表这条边最多被选一次
            add_edge(u, n + v, 1);
            add_edge(v, n + u, 1);
        }

        // --- 求解与判断 ---
        long long flow = max_flow(s, t);

        if (flow == total_d) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O((N+M)\sqrt{N})$ 。我们的网络流图有 $V = 2N+2$ 个点， $E = 2N + 2M$ 条边。Dinic 算法在一般图上的复杂度是 $O(V^2E)$ ，但在这种类似二分图匹配的单位容量网络上，表现会更好，通常可以达到 $O(E\sqrt{V})$ 。代入我们的 $V$ 和 $E$ ，就得到了这个复杂度。对于本题的数据范围来说，是完全可以接受的，喵~
空间复杂度: $O(N+M)$ 。主要是邻接表 adj 和Dinic算法中一些辅助数组 level, iter 的开销。邻接表需要存储 $2N+2M$ 条边，所以空间复杂度和图的点数与边数成正比。

知识点总结

这道题是一个非常好的例子，展示了如何将一个看似组合和构造的问题，转化为一个网络流模型来求解。

问题建模: 核心是将抽象的“度数约束”转化为具象的“流量约束”。为每个顶点拆分出“供给”和“需求”两个角色（U_i 和 V_i），是解决这类问题的经典技巧。
网络流的应用: 这道题是网络流在“带度数约束的子图存在性”问题上的典型应用。这个模型可以推广到更一般的情况，比如每个点的度数有上下界等。
Dinic算法: 作为求解最大流问题的高效算法，Dinic 是算法竞赛中的必备工具。它通过 BFS 分层和 DFS 多路增广，并结合当前弧优化，实现了优秀的性能。

希望这篇题解能帮助主人更好地理解网络流的奥秘！如果还有什么问题，随时可以再来问我哦，喵~

1or2 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

Step 1: 初始的思考和约束 ​

Step 2: 核心思想——流量分配 ​

Step 3: 构建网络流模型 ​

Step 4: 求解与判断 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​