백준 11960번 - Max Flow

https://www.acmicpc.net/problem/11960

11960번: Max Flow

 

• 필요한 배경지식

최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍

 

 

• 문제 해결 방법

이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 특정 헛간에서 펌핑된 우유의 양을 구할 수 있습니다.

 

농장 관리 문제와 다른점은 간선이 아니라 노드에 값이 더해져야 한다는 것과

업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
#define MAX 50000
using namespace std;

int N, M;
int ac[MAX+1][21]{};
int dpt[MAX+1]{};
vector<int> adj[MAX+1]{};
int cnt[MAX+1]{};

int num = 0;
void dfs(int now, int parent) {
    dpt[now] = dpt[parent] + 1;
    ac[now][0] = parent;

    for (int i = 1; i <= 20; i++)
        ac[now][i] = ac[ac[now][i-1]][i-1];

    for (auto next : adj[now]) {
        if (next == parent) continue;
        dfs(next, now);
    }
}

int lca(int x, int y) {
    if (dpt[x] > dpt[y]) swap(x, y);
    for (int i = 20; i >= 0; i--) { 
        if (dpt[y] - dpt[x] >= (1 << i)) 
            y = ac[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (ac[x][i] != ac[y][i]) {
            x = ac[x][i];
            y = ac[y][i];
        }
    }
    return ac[x][0];
}

void dfs2(int now, int par){
    for(auto &i : adj[now]){
        if(i != par) dfs2(i, now), cnt[now] += cnt[i];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    int a,b;
    for(int i=1; i<N; i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0);

    while(M--){
        cin>>a>>b;
        int l = lca(a,b);
        cnt[a]++;
        cnt[b]++;
        cnt[l]--;
        cnt[ac[l][0]]--;
    }

    dfs2(1, 0);
    cout << *max_element(cnt + 1, cnt + N + 1);
}