Codeforces 1082G. Petya and Graph (Mincut)

日付: 11月 30, 2018

[Problem - 1082G - Codeforces](https://codeforces.com/contest/1082/problem/G)
## Problem
Given a simple graph <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G with <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n vertices and <math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>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:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>3</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>m</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">1\le n \le 10^3, 1\le m \le 10^3</annotation></semantics></math>1≤n≤103,1≤m≤103

## 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 <math><semantics><mrow><msup><mi>G</mi><mo mathvariant="normal">′</mo></msup></mrow><annotation encoding="application/x-tex">G&#x27;</annotation></semantics></math>G′:
1. Add an edge from <math><semantics><mrow><mi>s</mi><mi>o</mi><mi>u</mi><mi>r</mi><mi>c</mi><mi>e</mi></mrow><annotation encoding="application/x-tex">source</annotation></semantics></math>source to each vertice that represents an edge in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G with capacity equal to the edge's value.
2. Add an edge from each vertice that represents a vertice in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G to <math><semantics><mrow><mi>s</mi><mi>i</mi><mi>n</mi><mi>k</mi></mrow><annotation encoding="application/x-tex">sink</annotation></semantics></math>sink with capacity equal to the vertice's value.
3. Add edges from vertices representing edges in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G to vertices representing their incident vertices in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G with infinite capacity.

The answer is the sum of values of edges in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G minus the **minimum cut** of <math><semantics><mrow><msup><mi>G</mi><mo mathvariant="normal">′</mo></msup></mrow><annotation encoding="application/x-tex">G&#x27;</annotation></semantics></math>G′.

*Simple proof*

One observation is that: **If a vertice is removed, all its incident edges must also be removed.** In graph <math><semantics><mrow><msup><mi>G</mi><mo mathvariant="normal">′</mo></msup></mrow><annotation encoding="application/x-tex">G&#x27;</annotation></semantics></math>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 <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G. Cutting an edge in #3 means allowing the corresponding vertice in <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>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)

コメント

コメントを投稿