백준18586 Salty Fish

작성일 | In

문제 링크

  • http://icpc.me/18586

사용 알고리즘

  • Max-Flow Min-Cut Theorem
  • Tree DP?

시간복잡도

  • $O(N \log^2 N)$

풀이

(1) 카메라를 매수하고 정점을 선택하는 것과 (2) 정점을 포기하는 것, 두 가지 행동을 적절히 해서 이득을 최대화(손실을 최소화)하는 것이 문제의 목적입니다. 모든 정점을 다 먹는 것을 기본으로 하고, 각 행동을 선택함으로써 손해를 보게 되는 비용을 생각해봅시다.
카메라를 매수하는 경우 카메라의 가격인 $C_i$만큼 손해를 보고, 정점을 포기하는 경우 해당 정점에 있는 사과의 개수인 $A_i$만큼 손해를 봅니다.


Source와 카메라를 가중치가 $C_i$인 간선, 카메라와 그 카메라가 담당하는 정점을 가중치가 $\infty$인 간선, 정점과 Sink를 가중치가 $A_i$인 간선으로 이어주면 Min Cut문제가 됩니다. 이때 정답은 $(\sum A_i - MinCut)$이 됩니다. Max Flow = Min Cut이므로 정답은 $(\sum A_i - MaxFlow)입니다.$
그래프의 크기가 매우 크기 때문에 전형적인 플로우 알고리즘을 사용하면 안 되고, 그래프의 형태에 맞게 적절한 알고리즘을 설계해야 합니다.

기본적인 컨셉은 Ford-Fulkerson처럼 유량을 흘릴 수 있는 곳을 찾아서 흘리는 방식으로 진행합니다.
dp(v, d): v를 루트로 하는 서브트리의 정점 중, 1번 정점과 d만큼 떨어져 있는 정점에서 Sink로 가는 간선들의 잔여 유량의 합으로 정의합시다.

DFS를 하면서 아래에 있는 정점부터 처리할 것입니다.
현재 정점 v에 달려있는 카메라는 깊이가 dep[v] + k[i]인 정점까지 관리할 수 있습니다. 흘릴 수 있는 가장 깊은 곳부터 유량을 흘리는 것이 이득입니다. 그러므로 dp(v)를 std::map으로 관리하면서, prev(upper_bound)를 구해 유량을 흘려주면 됩니다.

현재 정점의 dp값을 부모 정점과 합쳐주는 것은 Small to Large를 이용하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll n, m, a[303030];
vector<int> g[303030];
vector<p> ca[303030];
int par[303030], dep[303030];
map<int, ll> mp[303030];

void init(){
    for(int i=1; i<=n; i++){
        g[i].clear();
        ca[i].clear();
        mp[i].clear();
        a[i] = par[i] = dep[i] = 0;
    }
}

ll flow;
void merge(map<int, ll>  mp1, map<int, ll>  mp2){
    if(mp1.size() < mp2.size()) swap(mp1, mp2);
    for(auto i : mp2) mp1[i.x] += i.y;
}
void dfs(int v){
    dep[v] = dep[par[v]] + 1;
    for(auto i : g[v]) dfs(i);

    mp[v][dep[v]] += a[v];
    for(auto i : g[v]) merge(mp[v], mp[i]);

    for(auto i : ca[v]){
        ll ff = i.y;
        while(ff && mp[v].size()){
            auto it = mp[v].upper_bound(dep[v] + i.x);
            if(it == mp[v].begin()) break; --it;
            ll now = min(ff, it->y);
            flow += now; ff -= now; it->y -= now;
            if(!it->y) mp[v].erase(it);
        }
    }
}

void solve(){
    cin >> n >> m; init();
    for(int i=2; i<=n; i++){
        cin >> par[i]; g[par[i]].push_back(i);
    }
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=m; i++){
        int x, k, c; cin >> x >> k >> c;
        ca[x].emplace_back(k, c);
    }
    flow = 0; dfs(1);
    cout << accumulate(a+1, a+n+1, 0ll) - flow << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}