Codeforces 1082G. Petya and Graph (Mincut)

日付: 11月 30, 2018

[Problem - 1082G - Codeforces](https://codeforces.com/contest/1082/problem/G)
## Problem
Given a simple graph $G$ with $n$ vertices and $m$ edges.  Every vertice and every edge has a value. The task is to choose a subgraph such that, the sum of values of edges minus the sum of values of vertices is maximum.

**Constraints:** $1\le n \le 10^3, 1\le m \le 10^3$

## Solution
Notice that this graph is undirected, if we simply split the edge into two directed edge, it is hard to guarantee that the two edges are both chosen or both not chosen.

The key trick of dealing with this problem is to **treat edges as vertices**. The new vertice now has two directed edges connected to the two incident vertices of the original edge. Let us construct such a network-flow graph $G'$:
1. Add an edge from $source$ to each vertice that represents an edge in $G$ with capacity equal to the edge's value.
2. Add an edge from each vertice that represents a vertice in $G$ to $sink$ with capacity equal to the vertice's value.
3. Add edges from vertices representing edges in $G$ to vertices representing their incident vertices in $G$ with infinite capacity.

The answer is the sum of values of edges in $G$ minus the **minimum cut** of $G'$.

*Simple proof*

One observation is that: **If a vertice is removed, all its incident edges must also be removed.** In graph $G'$, an edge in case #3 is not cut represents that this vertice is not in the subgraph and we must cut all edges connecting it (i.e. make its flow be 0).
Cutting an edge in #1 means removing the corresponding edge in $G$. Cutting an edge in #3 means allowing the corresponding vertice in $G$ to remain in the subgraph.

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

template <typename T> struct MaxFlow {
    struct Edge { int u, v; T c, f; };
    const T eps = (T)1e-9;
    vector<Edge> E;
    int n, src, sink;
    vector<vector<int>> G;
    vector<int> P, D;
    T flow = T();
    MaxFlow(int n, int src, int sink): n(n), src(src), sink(sink), G(n), P(n), D(n) {}

void clear_flow() { for (auto &e : E) e.f = T(); flow = T(); }
    void reduce() { for (auto &e : E) e.c -= e.f; }
    void add_edge(int u, int v, T cap) {
        assert(0 <= u && u < n && 0 <= v && v < n);
        G[u].push_back(E.size()), E.push_back({u, v, cap, T()});
        G[v].push_back(E.size()), E.push_back({v, u, T(), T()});
    }
    bool expath() {
        fill(D.begin(), D.end(), -1);
        queue<int> Q;
        Q.push(sink), D[sink] = 0;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int id : G[u]) {
                const Edge &e = E[id], &b = E[id ^ 1];
                if (b.c - b.f > eps && D[e.v] == -1) {
                    D[e.v] = D[e.u] + 1, Q.push(e.v);
                    if (e.v == src) return true;
                }
            }
        }
        return false;
    }
    T dfs(int u, T w) {
        if (u == sink) return w;
        for (int &i = P[u]; i < int(G[u].size()); i++) {
            int id = G[u][i];
            const Edge &e = E[id];
            if (e.c - e.f > eps && D[e.v] == D[e.u] - 1) {
                T t = dfs(e.v, min(e.c - e.f, w));
                if (t > eps) return E[id].f += t, E[id ^ 1].f -= t, t;
            }
        }
        return T();
    }
    const T max_flow() {
        while (expath()) {
            fill(P.begin(), P.end(), 0);
            T tot = T();
            for (;;) {
                T add = dfs(src, numeric_limits<T>::max());
                if (add <= eps) break;
                tot += add;
            }
            if (tot <= eps) break;
            flow += tot;
        }
        return flow;
    }
    vector<int> min_cut() {
        max_flow();
        vector<int> R(n);
        for (int i = 0; i < n; i++) R[i] = (D[i] != -1);
        return R;
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int src = 0, sink = n + m + 1;
    MaxFlow<long long> mf(n + m + 2, src, sink);
    auto ans = 0LL;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        mf.add_edge(m + i, sink, x);
    }
    const long long INF = 1LL << 45;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        ans += w;
        mf.add_edge(src, i, w);
        mf.add_edge(i, u + m, INF);
        mf.add_edge(i, v + m, INF);
    }
    ans -= mf.max_flow();
    printf("%lld\n", ans);
}
```

KONGROOの基地

このブログを検索

Codeforces 1082G. Petya and Graph (Mincut)

コメント

コメントを投稿