백준 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);
}