G. Petya and Graph - 题解

比赛与标签

比赛: Educational Codeforces Round 55 (Rated for Div. 2) 标签: flows, graphs 难度: *2400

题目大意喵~

主人，这道题是这样子的呐：

我们有一个可爱的图，它有 n 个顶点和 m 条边。每个顶点 i 都有一个正整数权重 a_i，可以看作是选择这个点的“成本”哦。每条边 j 也有一个正整数权重 w_j，可以看作是选择这条边的“收益”~

我们的任务是，从这个大图中选出一个子图。一个子图就是由一部分顶点和一部分边组成的。但是有一个小小的规则：如果你选择了一条边，那么这条边的两个端点也必须被选中，不然边就没地方待了呀！

子图的总权重被定义为：(所有被选中边的权重之和) - (所有被选中顶点的权重之和)。

我们的目标就是找到一个子图，让这个总权重最大化！当然，我们也可以选择一个空子图，那样的话权重就是 0 啦。

输入:

第一行是顶点数 n 和边数 m。
第二行是 n 个顶点的成本 a_i。
接下来 m 行，每行描述一条边，包括它的两个端点 u, v 和它的收益 w。

输出:

一个整数，表示能得到的最大子图权重。

解题思路喵！

当看到这种“选择一些东西获得收益，但选择它们需要付出一些成本，并且选择之间还有依赖关系”的问题时，猫娘的直觉告诉我，这很可能是一个最小割模型可以解决的问题，喵~！

具体来说，这类问题被称为“最大权闭合子图”问题。我们的目标是最大化 Σ(选中的边权) - Σ(选中的点权)。

直接最大化这个式子有点困难，但我们可以把它转换一下。假设我们把所有边的权重加起来，得到一个总收益 TotalW。那么我们想最大化的值可以写成： Maximize( Σ(选中的边权) - Σ(选中的点权) )

这等价于： Maximize( TotalW - (TotalW - Σ(选中的边权)) - Σ(选中的点权) )

因为 TotalW 是个常数，所以这又等价于： TotalW - Minimize( (Σ(所有边权) - Σ(选中的边权)) + Σ(选中的点权) )

我们再仔细看看括号里的部分： (Σ(没选的边权)) + (Σ(选中的点权))。这不就是我们选择一个方案所付出的“代价”嘛！代价分为两种：

放弃的收益: 对于每一条我们没有选择的边，我们损失了它的权重 w_j。
付出的成本: 对于每一个我们选择了的顶点，我们付出了它的成本 a_i。

我们的目标就是让这个总代价最小！而“最小代价”正好可以用网络流中的“最小割”来求解，太奇妙了，对吧？

最小割建模方法如下喵~

创建源点 S 和汇点 T: 这是网络流模型的标准开场~ S 代表“选择”的源头，T 代表“放弃”的归宿。
表示收益 (边权):
- 对于原图中的每一条边 j（连接 u 和 v，权重为 w_j），我们创建一个新的节点，叫它 EdgeNode_j。
- 我们从源点 S 向 EdgeNode_j 连一条容量为 w_j 的边。
- 含义: 这条 (S, EdgeNode_j) 边如果被割断，表示我们放弃了选择这条边，代价就是 w_j。如果它没被割断，意味着 EdgeNode_j 和 S 在同一个集合里，代表我们打算选择这条边。
表示成本 (点权):
- 对于原图中的每一个顶点 i（权重为 a_i），我们从顶点 i 对应的节点向汇点 T 连一条容量为 a_i 的边。
- 含义: 这条 (i, T) 边如果被割断，表示我们选择了这个顶点，代价是 a_i。如果它没被割断，意味着节点 i 和 T 在同一个集合里，代表我们放弃了这个顶点。
表示依赖关系:
- “选边必选点”这个规则要怎么体现呢？很简单！如果选了边 j，就必须选它的端点 u 和 v。
- 在我们的模型里，"选"意味着节点和 S 在一侧。所以，如果 EdgeNode_j 和 S 在一侧，那么节点 u 和 v 也必须和 S 在一侧。
- 为了强制实现这一点，我们从每个 EdgeNode_j 向它对应的两个端点 u 和 v 分别连一条容量为无穷大的边。
- 含义: 因为这条边的容量是无穷大，最小割永远不会割断它。所以，如果 EdgeNode_j 在 S 侧，而 u 或 v 在 T 侧，就会形成一条从 S 侧到 T 侧的无穷大容量的边，这不可能是最小割。因此，只要 EdgeNode_j 被划入 S 侧，u 和 v 也必然被划入 S 侧，完美地实现了我们的依赖关系！

总结一下建图过程:

源点 S，汇点 T。
m 个代表边的节点，n 个代表点的节点。
S -> EdgeNode_j，容量 w_j。
EdgeNode_j -> u，容量 ∞。
EdgeNode_j -> v，容量 ∞。
i -> T，容量 a_i。

建好图后，我们求从 S 到 T 的最大流。根据最大流最小割定理，最大流的值就等于最小割的容量。这个最小割的值，就是我们上面推导出的 Minimize( (Σ(没选的边权)) + (Σ(选中的点权)) )。

所以，最终的答案就是： 最大子图权重 = (所有边的权重总和) - (S到T的最大流)

这下思路就完全清晰啦，可以开始写代码了喵！

代码实现喵~

cpp

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

using namespace std;
typedef long long ll;

// 一个标准的Dinic算法模板，用来求最大流的说
struct Dinic {
    struct Edge {
        int to, rev;
        ll cap, flow;
    };

    vector<vector<Edge>> graph;
    vector<int> level, ptr;
    int n;

    Dinic(int nodes) {
        n = nodes;
        graph.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int from, int to, ll cap) {
        Edge forward = {to, (int)graph[to].size(), cap, 0};
        Edge backward = {from, (int)graph[from].size(), 0, 0}; // 反向边容量初始为0
        graph[from].push_back(forward);
        graph[to].push_back(backward);
    }

    // BFS分层，判断是否存在增广路
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const Edge &e : graph[u]) {
                if (level[e.to] == -1 && e.flow < e.cap) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    // DFS在分层图上寻找增广路并增广
    ll dfs(int u, int t, ll flow) {
        if (u == t || flow == 0)
            return flow;
        // 当前弧优化，ptr[u]记录当前节点u搜索到了哪条边
        for (int &i = ptr[u]; i < graph[u].size(); i++) {
            Edge &e = graph[u][i];
            if (level[e.to] == level[u] + 1 && e.cap > e.flow) {
                ll pushed = dfs(e.to, t, min(flow, e.cap - e.flow));
                if (pushed > 0) {
                    e.flow += pushed;
                    graph[e.to][e.rev].flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    // 主函数，计算从s到t的最大流
    ll max_flow(int s, int t) {
        ll total_flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (ll pushed = dfs(s, t, LLONG_MAX)) {
                total_flow += pushed;
            }
        }
        return total_flow;
    }
};

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

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

    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 节点总数：源点(1) + 汇点(1) + 顶点(n) + 边节点(m)
    int total_nodes = n + m + 2;
    int source = 0;
    int sink = n + m + 1;
    Dinic dinic(total_nodes);

    ll total_edge_weight = 0;

    // 建立边节点相关的边
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        total_edge_weight += w; // 累加所有边的权重

        // 边节点编号从 n+1 开始
        int edge_node = n + 1 + i;
        
        // 1. 从源点 S 连接到边节点，容量为边的权重
        dinic.add_edge(source, edge_node, w);
        
        // 2. 从边节点连接到其两个端点，容量为无穷大 (用一个很大的数表示)
        // 这里的1e18足够大了
        dinic.add_edge(edge_node, u, (ll)1e18);
        dinic.add_edge(edge_node, v, (ll)1e18);
    }

    // 建立顶点相关的边
    for (int i = 1; i <= n; i++) {
        // 3. 从顶点连接到汇点 T，容量为顶点的成本
        // 顶点编号是1-based, a数组是0-based
        dinic.add_edge(i, sink, a[i-1]);
    }

    // 计算S到T的最大流，也就是我们模型中的最小割
    ll min_cut = dinic.max_flow(source, sink);

    // 最终答案 = 总收益 - 最小代价
    ll ans = total_edge_weight - min_cut;
    cout << ans << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(Dinic) 的说。Dinic算法在一般图上的理论上界是 O(V^2 * E)，其中 V 是点数，E 是边数。在我们构建的图中，V = n + m + 2，E = O(n + m)。虽然理论复杂度看起来很高，但对于这种特殊的二分图结构的网络，Dinic算法的实际表现通常要好得多，足以在规定时间内跑完，真是太棒了喵~
空间复杂度: O(V + E) 的说。我们需要存储网络流图的邻接表，所以空间复杂度和图的点数和边数成正比，也就是 O(n + m)。

知识点与总结

这道题真是一道非常经典的教学题，让我们可以把一个看似复杂的优化问题，通过巧妙的转化，变成一个标准的网络流问题来解决，喵~

核心思想：最大权闭合子图 这是一个非常重要的模型！当你遇到需要在一堆物品中做选择，每个物品有收益和成本，且选择之间存在“A依赖于B”（选A必须选B）的关系时，就要立刻想到这个模型！
转化技巧：最大化 -> 最小化 最大化 收益 - 成本 的问题，可以转化为 总收益 - 最小化(放弃的收益 + 付出的成本)。这个转化是解决这类问题的关键一步，一定要记住哦！
建模方法：最小割
- 收益: 从源点 S 连出，容量为收益值。割断代表放弃。
- 成本: 连向汇点 T，容量为成本值。割断代表接受。
- 依赖关系: 从依赖者连向被依赖者，容量为无穷大。这确保了它们在最小割中要么都在 S 侧，要么被依赖者在 T 侧。
算法实现：Dinic Dinic是解决最大流问题的常用高效算法，它的分层图和当前弧优化思想值得我们学习和掌握。

希望这篇题解能帮助到你，如果还有不明白的地方，随时可以再来问猫娘哦！一起加油，攻克更多有趣的算法题吧，喵~！

G. Petya and Graph - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​