블로그 옮겼습니다

문제 링크 노드의 수가 100개 이하인 두개의 트리 g1, g2 가 주어진다. 두 트리의 루트 노드는 모두 1번 노드이다. 두 트리의 최대 공통 노드 수를 출력하는 문제이다. 쉽게 말해서 각 노드에 대해서 자식 노드들의 순서를 요리 조리 바꿔도 여전히 같은 트리이기 때문에 각 노드의 자식들의 순서를 요리 조리 바꿨을 때 두 트리중 모양이 일치하는 가장 노드가 많은 부분 트리의 노드 수를 구하는 문제이다. dp[a][b] : 트리 g1에서 노드 a를 루트로 하는 서브트리와, 트리 g2에서 노드 b를 루트로 하는 서브트리의 최대 공통 노드 수 라고 부분 문제를 정의하면 트리 dp 로 해결할 수가 있다. 그렇다면 부분 문제 테이블의 하나의 셀을 어떻게 채울까? 답은 MCMF 이다. dp[a][b] 에서 a의 ..

http://codeforces.com/contest/277/problem/E 2 src = src; this->sink = sink; } bool spfa(){ vector inQ = vector(size, false); queue q; q.push(src); inQ[src] = true; dist[src] = 0; while(!q.empty()){ int here = q.front(); q.pop(); inQ[here] = false; for(int i = 0 ; i 0 && dist[here] + e.cost b.y;}vector points;int N;int NODE(int x){return 2 + x;}int IN(int x){return 2 * x;}int OUT(int x){return 2 ..

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2376 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int inf = 0x3c3c3c3c;const l..