PS와 개발을 공부하자

http://codeforces.com/contest/277/problem/E2 <= N <= 4002차원 좌표 평면상에 N개의 점이 주어진다. 점 i와 점 j가 있을 때 yi < yj 일 때만 점 i 에서 점 j 로 간선을 이을 수가 있다.만약 점 i 에서 점 j 로 간선을 잇게 되면 점 i는 점 j의 부모노드가 되며 이 때 드는 비용은점 i와 점 j의 거리만큼이다. 이런식으로 N개의 점을 노드로하는 이진트리를 만들 때의 최소 비용을구하는 문제이다. 물론 이진트리는 각각의 노드들의 자식의 수가 2개 이하인 트리이다.N의 제한에서도 플로우의 냄새가 강하다. 뿐만 아니라 주어진 제한이 있으며그 제한 내에서의 비용을 최소화 하는 문제, 플로우 중에서도 MCMF 라는 느낌을 받을 수가 있다.그렇다면 주어진 제..

https://www.acmicpc.net/problem/9169123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int INF = 0x3c3c3c3c;const long long INFL = 0x3c3c3c3c3c3c3c3c;struct edge{int to, cap, rev;};vector G[303];void connect(int from, int to, int cap){ G[from].push_back({to, cap, (int)G[to]...

https://www.acmicpc.net/problem/236512345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int INF = 0x3c3c3c3c;const long long INFL = 0x3c3c3c3c3c3c3c3c; struct edge{int to, ..

https://www.acmicpc.net/problem/1444하나의 단어는 알파벳 소문자하나와 대문자 하나로 이루어진다. 소문자가 앞에 나오는 경우와 뒤에 나오는 경우이렇게 두가지 경우가 있다. 알파벳 소문자와 대문자가 번갈아 나오는 문장이 입력으로 들어올 때이 문장은 몇 개의 단어로 이루어 질 것이다. 이 때 여러가지 케이스가 있을 텐데 그중 최소 단어 개수를 찾는 문제이다.예를 들어 aAbAc 가 있으면 aA, bB, Ac 로 이루어 졌을 수도 있고 aA, Ab, Ac 로 이루어 졌을 수도 있는 것이다.이 문제는 결국 최소 정점 덮개 이다. 최소 정점 덮개란 이분 그래프에서 모든 간선이 자신과 접한 두 정점 중최소한 하나는 선택하도록 할 때 최소로 선택하는 정점의 수이다. 그니까 하나의 정점을 선..

N개의 컴포넌트들이있고 판떼기가 하나있다. 판떼기는 앞면과 뒷면이있다. 각 컴포넌트를 판떼기에 모두 붙이고싶은데 하나의 컴포넌트를 앞면에 붙이는 비용과 뒷면의 붙이는 비용은 다르고각 컴포넌트마다도 비용이 또 다르다.그리고 특정 컴포넌트들은 무조건 앞면 혹은 뒷면에 부착해야 된다는 조건이 주어진다.-1 이면 뒷면에, 1이면 앞면에 붙여야하며 0이면 어떤면에 붙여도 상관없다는 것이다.그리고 M개의 제한이 주어지는데 각 제한의 내용은 특정 두 컴포넌트를 다른 면에 붙였을 때에는추가적인 비용이 발생한다는 것이다. 각 제한마다 두 컴포넌트와 추가 비용은 다르다.이 때 N개의 컴포넌트를 모두 판떼기에 붙이는 최소 비용을 구하여라.이 문제는 min-cut 문제이다. source -> 컴포넌트 -> sink 와 같은 ..