1. 플로우 == 백준 최대 유량
2. 레드블랙 트리 == 백준 TV Show 어쩌구

빨강/검정 중 하나의 색인 K개의 노드 중 3개를 골라 색을 예측하는 것을 N명의 학생이 할 때, 모든 학생의 과반수의 예측이 맞을 수 있는가? 가능하다면 그런 경우를 출력

2-sat이다.

예측이 a, b, c라고 할 때 (a or b) and (b or c) and (c or a) 가 성립해야 함

1. 파괴

N x N의 격자에 코치 K명이 앉아 있을 때, 행 또는 열에 평행하게 파괴 광선을 쏠 수 있다. 최소로 쏴서 코치를 파괴할 때 사용 횟수 구하기

source → 행 (유량 1), 행 → 열 (코치마다, 유량 $\infin$), 열 → sink (유량 1)

max flow min cut 정리에 의해 위 그래프에서 플로우를 돌리면 해결 가능

1. 거짓말쟁이 == 백준 L 타일

검-흰 쌍을 간선으로 생각하고, (백준 기준 메모리가 빡빡하므로) 각 간선에 검은색 타일 기준으로 번호를 매기면 2-sat으로 판별할 수 있다.

검은색 기준 (위 xor 아래) and (왼 xor 오), 흰색 기준 4C2개 쌍에 대해 (~a or ~b)

추가로 검은색 주변에 2개의 흰 타일, 흰색 주변에 검은색 타일, 검은색 * 2 == 흰 정도를 확인해주면 ac를 받을 수 있다.

1. 경찰서 == 백준 경찰서

브루국에는 도시 V 개가 있고, 이들을 잇는 단방향 도로 E개가 있다. 브루국의 독재자 반딧불은 도시 중 몇 개에 경찰서를 설치해서 도시들을 통제하려 한다. 도시 i에 설치한 경찰서가 도시 j를 통제하려면 도시 i에서 j로 갔다가, 다시 돌아오는 경로가 존재해야 한다. 각 도시마다 경찰서를 짓는 비용이 주어진다. 모든 도시에 통제하는 경찰서가 하나 이상 존재하게 하기 위한 최소 비용은 얼마일까?

scc마다 최소 비용을 구해 주면 된다.

1. 프로듀스 IOI == 백준 아이돌

2-sat 기본 문제다. 해를 구할 필요도 없다.

1. 절도 == 백준 ATM

각 노드마다 돈이 있고, S로 들어가서 주어진 P개의 노드 중 하나로 나올 때 얻을 수 있는 최대 돈