정화 코딩

https://www.acmicpc.net/problem/11408 기본적인 최대 유량 문제 풀듯이 하되, 각 단계마다 현재 잔여 그래프에서 최단 거리 알고리즘을 이용해 최소 비용 증가 경로를 찾고, 그 경로로 유량을 흘려준다. 최단 거리를 구할 때는 벨만 포드 알고리즘을 약간 변형시켜 평균 실행 시간을 줄인 SPFA를 사용하였다. // Reference: green55 teamnote// https://github.com/green5555/Teamnote/blob/master/TeamNote/MCMF.cpp#include using namespace std;typedef long long ll;typedef pair pll;//O(VEf), Average = O(Ef)const int MAX=2010;..

https://www.acmicpc.net/problem/11377 이렇게 중간 노드를 하나 만들어서 거기로 k만큼 흘려주도록 모델링하면 이렇게 된다. // Reference: green55 teamnote// https://github.com/green5555/Teamnote/blob/master/TeamNote/Ed-Karp.cpp#include using namespace std;typedef pair pii;const int MAX = 2010, INF = INT_MAX;struct maxflow { struct edge { int next, cap, flow = 0, rev_idx; edge() {} edge(int n, int c) : next(n)..

https://www.acmicpc.net/problem/5419 스위핑 아이디어우리가 하고 싶은 것: 각 섬마다 자신보다 북서쪽에 있는 섬들이 몇 개인지 -> 그것들의 합을 구하면 정답그러므로 섬들을 x 기준 오름차순, y 기준 내림차순으로 정렬해두자.그렇게 정렬해둔 다음에, 앞에서부터 보면서 각 섬 기준 북서쪽에 있는 섬들이 몇 개인지 셀 때 지금까지 본 섬 중 자기보다 y값이 크거나 같은 섬이 몇 개였는지만 세면 된다.자기 기준으로 북서쪽 섬이 몇 개인지 확인 후, 자기 섬도 등록해야 한다. 세그먼트 트리 아이디어지금까지 본 섬들 중 자기보다 y값이 크거나 같은 섬이 몇 개인지를 빠르게 구하기 위해서 세그먼트 트리를 사용해야 한다.-> 세그먼트 트리에 저장해야 하는 값: 지금까지 본 섬들의 y값 분..

https://www.acmicpc.net/problem/4196 첨엔 그냥 scc 개수를 구해서 틀렸다. 그런데 1과 2가 같은 scc이고 3과 4가 같은 scc이면서 2에서 3으로 가는 간선이 있는 경우를 생각해보면, scc 개수는 2이지만 답은 1이다.왜냐하면 1을 넘어뜨리면 같은 scc인 2도 자연스럽게 넘어지고 따라서 3, 4도 넘어지기 때문이다. 따라서 이 문제는 scc를 구한 뒤, in-degree가 0인 (다른 것에 의해서 넘어지지 않는) scc의 개수만을 세야 한다. #include #include #include using namespace std;vector> adj1;vector> adj2;vector vst;stack stk;vector scc;int idx;void dfs1(in..

강한 연결 요소 - Strongly Connected Component (SCC)방향 그래프에서 모든 정점 쌍 사이에 경로가 존재할 때, 그 그래프는 강하게 연결되어 있다고 한다.방향 그래프에서 모든 정점 쌍 사이에 경로가 존재하는 최대 부분 그래프를 강한 연결 요소라고 한다. Kosaraju 알고리즘: scc를 구하는 알고리즘adj1: 원래 방향 그래프의 인접 리스트adj2: 원래 그래프의 간선을 모두 반대로 뒤집은 그래프의 인접 리스트dfs1: 원래 그래프를 dfs로 탐색함. 탐색하면서 완료 정점을 stack에 담음.dfs2: stack의 정점들을 pop하면서 반전 그래프를 dfs로 탐색함. => dfs2 호출 횟수가 강한 연결 요소 개수 #include #include #include #includ..

https://www.acmicpc.net/problem/3295 그래프의 구조가 링이거나 선형 배열이라는 것은 그래프를 이루는 각 노드들의 in-degree도 최대 1이고 out-degree도 최대 1이라는 것이다. 그리고 k개의 노드로 이루어진 링의 가치가 k이고 k개의 노드로 이루어진 선형 배열의 가치가 k라는 것은 어떤 그래프에서 각 노드의 in-degree도 최대 1이고 out-degree도 최대 1이 되도록 간선들을 선택했을 때의 간선 개수 자체가 가치가 된다는 뜻이다. 따라서 왼쪽에 출발 노드 집합을 두고 오른쪽에 도착 노드 집합을 두고 최대 이분 매칭을 구하면 된다. // Reference: green55 teamnote// https://github.com/green5555/Teamno..

https://www.acmicpc.net/problem/1867 목적은 모든 돌멩이를 제거하는 것이다. 하나의 돌멩이는 하나의 행과 하나의 열 위에 놓여 있다. 그 말은, 해당 돌멩이를 제거하기 위해서는 그 행에서 뛰거나 그 열에서 뛰어야 한다는 뜻이다. 한 쪽에는 행 노드들이 있고 한 쪽에는 열 노드들이 있다고 생각해보면, 돌멩이는 하나의 행과 하나의 열을 연결해주는 간선의 역할을 한다고 생각할 수 있다. 따라서 이렇게 이분 그래프가 만들어진다. 여기서 모든 돌(간선)을 커버하기 위해 필요한 최소 정점 수는 이분 그래프에서의 최소 정점 커버 (Minimum Vertex Cover) 문제이며, 쾨니그 정리에 의해 이는 최대 이분 매칭의 크기와 같다고 한다. // Reference: green55 tea..

https://www.acmicpc.net/problem/11375 각 직원은 하나의 일만 담당할 수 있고, 각각의 일을 담당하는 사람은 한명이어야 한다.⇒ 한 쪽에는 직원 노드들이 있고 한 쪽에는 일 노드들이 있을 때, 담당 가능한 직원-일에 대해서 간선을 이어주면 이분 그래프가 만들어진다. 이 이분 그래프에서 최대 매칭 수를 구하면 정답이 나온다. // Reference: green55 teamnote// https://github.com/green5555/Teamnote/blob/master/TeamNote/BiMatch.cpp#include using namespace std;const int MAX = 2001;struct BiMatching { vector adj[MAX+5]; i..