블로그 옮겼습니다

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://www.acmicpc.net/problem/9169 123456789101112131415161718192021222324252627282930313233343536373839404142#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].size()}); G[to].push..

https://www.acmicpc.net/problem/2365 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#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;};int..

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

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