Codeforces 990F. Flow Control (Tree + DP)

日付: 12月 20, 2018

[Problem - 990F - Codeforces](https://codeforces.com/contest/990/problem/F)
## Problem
Given a connected undirected simple graph. Each vertex has a value $S_u$, if $S_u < 0$ vertex $u$ should have in-flow $|S_u|$, if $S_u > 0$ vertex $u$ should have out-flow $|S_u|$. Calculate the flow of each edge.

**Constraints:** $1\le n, m \le 2 \cdot 10^5$

## Solution
At first it seems that this is a maximum-flow problem, but notice that $n$ is too large for any maximum-flow algorithm. 
And the key **observation** is that as long as the graph is connected and the sum of $S$ is 0, it is always possible to find a solution. This observation enables us to only consider an arbitrary spanning tree of the original graph. And this problem is reduced to a tree-dp problem.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int N = 2e5 + 5;
int n, m, S[N], Use[N], F[N], Ans[N], te = 0;
struct Edge { int u, v; } E[N];
vector<int> G[N];

void dfs(int u) {
    Use[u] = 1;
    int from = 0, to = 0;
    for (auto i : G[u]) {
        int v = E[i].u == u ? E[i].v : E[i].u;
        if (Use[v]) continue;
        dfs(v);
        Ans[i] = u == E[i].u ? F[v] : -F[v];
        if (F[v] < 0) to += -F[v];
        else from += F[v];
    }
    F[u] = S[u] + from - to;
}
int main() {
    scanf("%d", &n);
    FI(i, 1, n) scanf("%d", S + i);
    scanf("%d", &m);
    FI(i, 1, m) {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(te), G[y].push_back(te);
        E[te++] = {x, y};
    }
    dfs(1);
    if (F[1]) puts("Impossible");
    else {
        puts("Possible");
        FI(i, 0, m - 1) printf("%d\n", Ans[i]);
    }
}
```

KONGROOの基地

このブログを検索

Codeforces 990F. Flow Control (Tree + DP)

コメント

コメントを投稿