고급반 3주차 풀이 - 흐물흐물

1. [9659] 돌 게임 5 (Silver II)

1개를 가져가든, 3개를 가져가든 남은 돌의 홀짝성은 "항상" 바뀌게 됩니다.

패배 조건 (0개가 남은 상태)은 짝수이므로, 홀수라면 상근이가 이기고, 아니면 창영이가 이깁니다.

void Main(){
	ll x; cin >> x;
	if (x&1){ cout << "SK"; } else{ cout << "CY"; }
}

2. [9660] 돌 게임 6 (Gold V)

작은 수에 대해서 직접 돌려봅시다.

N	0	1	2	3	4	5	6	7	8	9	10
승자	CY	SK	CY	SK	SK	SK	SK	CY	SK	CY	SK

N = (0, 1, 2, 3)의 승자 배치와 N = (7, 8, 9, 10)일 때의 승자 배치가 같으니, 이 뒤는 N = (0, 1, 2, 3, 4, 5, 6)의 패턴을 계속 반복하게 됩니다.

그러니, N을 입력받아서 7로 나눈 나머지가 0 또는 2이면 CY, 아니면 SK를 출력하면 됩니다.

void Main(){
	ll n; cin >> n;
	if (n%7 == 0 || n%7 == 2){ cout << "CY"; } else{ cout << "SK"; }
}

3. [9661] 돌 게임 7 (Gold II)

작은 수에 대해서 직접 돌려보면 CY SK CY SK SK의 패턴이 반복되는 걸 볼 수 있고, 실제로 이렇게 내면 맞습니다.

즉, Proof by AC를 해주면 됩니다.

 

5 = 4+1임을 보면 4를 가져갈 때 1을 가져간다 등의 어떤 전략이 있는 것 같지만, 아직 증명은 해보지 않았습니다.

[TODO: 엄밀한 증명]

void Main(){
	ll n; cin >> n;
	if (n%5 == 0 || n%5 == 2){ cout << "CY"; }
	else{ cout << "SK"; }
}

4. [11868] 님 게임 2 (Platinum IV)

스프라그-그런디 연습 문제입니다.

돌이 \( X \)개인 님 게임의 그런디 수는 \( X \)이므로, 입력받은 모든 수들을 Bitwise XOR해준 뒤 0이라면 cubelover가, 아니면 koosaga가 승리함을 알 수 있습니다.

void Main(){
	int n; cin >> n;
	int res = 0;
	while (n--){ int x; cin >> x; res ^= x; }
	if (res == 0){ cout << "cubelover"; } else{ cout << "koosaga"; }
}

5. [4196] 도미노 (Platinum IV)

입력받은 방향 그래프를 가지고 Strongly Conected Components 를 만들어봅시다.

자명하게, 어떤 한 SCC 안에 있는 도미노 하나만 쓰러뜨려도 그 SCC 내의 다른 도미노들은 다 쓰러지게 됩니다.

또한, SCC를 만들고 난 뒤 그 SCC를 하나의 큰 정점으로 보면 DAG가 만들어지는데, 이 DAG에서 맨 위에 있느 정점들 (indegree = 0인 정점들)만 쓰러뜨려도 나머지는 알아서 쓰러지게 됩니다.

 

그러므로 indegree가 0인 SCC의 개수를 세주면 됩니다.

vector<int> adj[100020];

stack<int> stk; int scc[100020];
int ord, ind[100020]; bool chk[100020];
int dfs(int now){
	ord += 1; ind[now] = ord; stk.push(now);
	int res = ind[now];
	for (int nxt : adj[now]){
		if (ind[nxt] == 0){ res = min( res, dfs(nxt) ); }
		else if (scc[nxt] == 0){ res = min(res, ind[nxt]); }
	}
	if (res == ind[now]){
		while (!stk.empty()){
			int vtx = stk.top(); stk.pop();
			scc[vtx] = now;
			if (vtx == now){ break; }
		}
	}
	return res;
}

void Main(){
	int t; cin >> t;
	while (t--){
		int n, m; cin >> n >> m;
		while (m--){
			int v, w; cin >> v >> w;
			adj[v].push_back(w);
		}
		for (int i = 1; i <= n; i++){ if (ind[i] == 0){ int _ = dfs(i); } }
		int ans = 0;
		for (int v = 1; v <= n; v++){
			if (!chk[ scc[v] ]){ ans += 1; }
			chk[ scc[v] ] = 1;
		}
		for (int v = 1; v <= n; v++){
			for (int w : adj[v]){
				//cout << v << " -> " << w << ": " << scc[w] << ' ' << chk[ scc[w] ] << ' ' << ans << endl;
				if (scc[v] == scc[w]){ continue; }
				if (chk[ scc[w] ]){ ans -= 1; }
				chk[ scc[w] ] = 0;
			}
		}
		cout << ans << endl;
		for (int i = 1; i <= n; i++){ adj[i].clear(); scc[i] = 0; ind[i] = 0; chk[i] = 0; }
		ord = 0;
	}
}

6. [4013] ATM (Platinum II)

SCC를 만들고 보면, 어떤 SCC에 도달했을 때 항상 그 안에 있는 모든 ATM기에서 돈을 뽑아오는 게 최적입니다.

또한, 하나의 SCC 안에 레스토랑이 여러개 존재하더라도, 그 레스토랑까지 가면서 인출하는 액수는 동일합니다.

그러니 SCC를 만들고, SCC를 하나의 큰 정점으로 만들면서 '안에 있는 ATM기의 돈의 합'과 '안에 레스토랑이 있는가?'만 체크해주면 됩니다.

 

SCC를 정점으로 만들면 그래프는 DAG가 되니 DP를 아래와 같이 돌려주면 됩니다.

여기서 \( v \rightarrow w \)인 간선이 있다고 가정하겠습니다.

\( DP_{v} := v \)번 정점까지 오면서 인출할 수 있는 현금의 최대 액수

\( A_{v}, R_{v} := \) 각각 \( v \)번 정점 속 ATM기의 돈, \( v \)번 정점에 있는 레스토랑 개수 (0 or 1)

\( DP_{w} = \max_{v \rightarrow w} DP_{v} + A_{w} \)

답: \( \max_{R_{v} \ge 1} DP_{v} \)

vector<int> adj[500020];
ll arr[500020]; bool chk[500020];

stack<int> stk; int scc[500020];
int ord, ind[500020]; vector<int> scv;
int dfs(int now){
	ord += 1; ind[now] = ord; stk.push(now);
	int res = ind[now];
	for (int nxt : adj[now]){
		if (ind[nxt] == 0){ res = min( res, dfs(nxt) ); }
		else if (scc[nxt] == 0){ res = min(res, ind[nxt]); }
	}
	if (res == ind[now]){
		while (!stk.empty()){
			int vtx = stk.top(); stk.pop();
			scc[vtx] = now;
			arr[now] += arr[vtx]; chk[now] |= chk[vtx];
			if (vtx == now){ break; }
		}
		arr[now] /= 2;
		scv.push_back(now);
	}
	return res;
}

vector<int> sdj[500020]; int cnt[500020];
ll dp[500020]; bool cal[500020];
void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w);
	}
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int st, k; cin >> st >> k;
	while (k--){ int v; cin >> v; chk[v] = 1; }
	for (int i = 1; i <= n; i++){ if (ind[i] == 0){ int _ = dfs(i); } }
	for (int v = 1; v <= n; v++){
		for (int w : adj[v]){
			if (scc[v] == scc[w]){ continue; }
			cnt[ scc[w] ] += 1; sdj[ scc[v] ].push_back(scc[w]);
		}
	}
	queue<int> q;
	for (int v : scv){ if (cnt[v] == 0){ q.push(v); } }
	//for (int v : scv){ cout << "ARR " << v << " = " << arr[v] << endl; }
	ll ans = 0;
	while (!q.empty()){
		int now = q.front(); q.pop();
		if (now == scc[st]){ cal[now] = 1; }
		for (int nxt : sdj[now]){
			cnt[nxt] -= 1; if (cnt[nxt] == 0){ q.push(nxt); }
			cal[nxt] |= cal[now];
		}
		if (cal[now]){
			dp[now] += arr[now];
			for (int nxt : sdj[now]){ dp[nxt] = max(dp[nxt], dp[now]); }
			if (chk[now]){ ans = max(ans, dp[now]); }
			//cout << "DP " << now << " = " << dp[now] << endl;
		}
	}
	cout << ans << endl;
}

7. [3682] 동치 증명 (Platinum III)

어떤 두 명제 \( P, Q \)가 동치라는 건, \( v \rightarrow w \)를 모두 방향성 간선으로 연결했을 때 \( P, Q \)가 같은 SCC에 속했다는 것과 같습니다.

그러니 우리의 목표는 그래프 전체를 하나의 SCC로 만들어주는 것이 됩니다.

 

일단 SCC를 만들고 DAG를 만들어줍시다.

주의할 점은, 연결그래프가 아닐 수도 있습니다. 즉 DAG가 여러 개 나올 수도 있습니다.

 

설명의 편의상 여기서부터는 DAG = Irreducible DAG입니다. 즉, 하나의 컴포넌트로 이루어진 DAG입니다.

각각의 DAG 속 정점에 대해, indegree와 outdegree가 모두 0이 아닌 정점은 indegree 또는 outdegree가 0인 정점을 처리하면 알아서 처리되기 때문에 지금부터는 indegree와 outdegree가 모두 0인 경우만 고려해도 됩니다.

 

이제 각각의 DAG에서 indegree가 0인 정점들과 outdegree가 0인 정점들을 다 들고 온 뒤, 각각 \( I, O \)라는 정점 집합으로 정의해봅시다.

이들을 적절히 연결해주면 하나의 큰 사이클을 만들 수 있으므로, 모든 SCC를 지나는 사이클 → SCC들끼리 양방향으로 갈 수 있는 경로 → 그래프가 하나의 큰 SCC가 됨 의 결과를 얻을 수 있습니다.

이 때 필요한 최소 간선 개수는 \( \max (|I|, |O|) \)입니다.

 

그러니 SCC를 만들고, indegree가 0인 SCC와 outdegree가 0인 SCC의 개수를 세준 뒤, 둘 중 더 큰 값을 선택해주면 됩니다.

예외적으로, 그래프가 이미 1개의 SCC인 경우는 추가적인 연결이 필요 없으므로 0을 출력해야 합니다.

vector<int> adj[20020];

stack<int> stk; int scc[20020];
int ord, ind[20020]; vector<int> scv;
int dfs(int now){
	ord += 1; ind[now] = ord; stk.push(now);
	int res = ind[now];
	for (int nxt : adj[now]){
		if (ind[nxt] == 0){ res = min( res, dfs(nxt) ); }
		else if (scc[nxt] == 0){ res = min(res, ind[nxt]); }
	}
	if (res == ind[now]){
		while (!stk.empty()){
			int vtx = stk.top(); stk.pop();
			scc[vtx] = now;
			if (vtx == now){ break; }
		}
		scv.push_back(now);
	}
	return res;
}

pi2 cnt[20020];
void Main(){
	int t; cin >> t;
	while (t--){
		int n, m; cin >> n >> m;
		while (m--){
			int v, w; cin >> v >> w;
			adj[v].push_back(w);
		}
		for (int i = 1; i <= n; i++){ if (ind[i] == 0){ int _ = dfs(i); } }
		for (int v = 1; v <= n; v++){
			for (int w : adj[v]){
				if (scc[v] == scc[w]){ continue; }
				cnt[ scc[v] ].fr += 1; cnt[ scc[w] ].sc += 1;
			}
		}
		pi2 res = {0, 0};
		for (int v : scv){
			//cout << "SCC " << v << endl;
			if (cnt[v].fr == 0){ res.fr += 1; }
			if (cnt[v].sc == 0){ res.sc += 1; }
		}
		if (scv.size() == 1){ cout << 0 << endl; }
		else{ cout << max(res.fr, res.sc) << endl; }
		for (int i = 1; i <= n; i++){
			adj[i].clear(); ind[i] = 0; scc[i] = 0; cnt[i] = {0, 0};
		}
		ord = 0; scv.clear();
	}
}

8. [6086] 최대 유량 (Platinum IV)

문제 이름부터 스포일러입니다. '최대 유량'.

입력받은 대로 그래프를 만든 뒤, A에서 Z로 흐르는 최대 유량을 계산해주면 됩니다.

inline int idx(char c){ if (c <= 'Z'){ return c-'A'; } return c-'a'+26; }

int adj[60][60], src = idx('A'), snk = idx('Z'), nc = 52;
int dis[60];
void bfs(int st){
	memset(dis, -1, sizeof(dis)); dis[st] = 0;
	queue<pi2> q; q.push({st, 0});
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc;
		q.pop();
		for (int nxt = 0; nxt < nc; nxt++){
			if (adj[now][nxt] == 0){ continue; }
			if (dis[nxt] != -1){ continue; }
			dis[nxt] = dst+1; q.push({nxt, dis[nxt]});
		}
	}
}
int ptr[60]; int pth[60], pc;
bool chk[60];
bool dfs(int now, int idx){
	pth[idx] = now; chk[now] = 1;
	if (now == snk){ pc = idx; return 1; }
	for (int &nxt = ptr[now]; nxt < nc; nxt++){
		if (adj[now][nxt] == 0 || chk[nxt]){ continue; }
		if (dfs(nxt, idx+1)){ return 1; }
	}
	return 0;
}

void Main(){
	int n; cin >> n;
	while (n--){
		char v, w; int x; cin >> v >> w >> x;
		adj[idx(v)][idx(w)] += x;
		adj[idx(w)][idx(v)] += x;
	}
	ll ans = 0;
	while (1){
		bfs(src); if (dis[snk] == -1){ break; }
		for (int i = 0; i < nc; i++){ ptr[i] = 0; chk[i] = 0; }
		while (dfs(src, 0)){
			int res = 1e9;
			for (int i = 1; i <= pc; i++){
				int v = pth[i-1], w = pth[i];
				res = min(res, adj[v][w]);
			}
			for (int i = 1; i <= pc; i++){
				int v = pth[i-1], w = pth[i];
				adj[v][w] -= res; adj[w][v] += res;
			}
			ans += res;
		}
	}
	cout << ans;
}

9. [11378] 열혈강호 4 (Platinum III)

직원과 일을 매칭하는 이분 매칭 문제이므로, 최대 유량으로 해결해주면 될 것 같은 문제입니다.

\( s \rightarrow \text{ Worker } \rightarrow \text{ Work } \rightarrow t \)의 그래프를 만든 뒤, \( s \)에서 \( t \)로 흐르는 최대 유량을 구해주면 됩니다.

 

... 벌점이 있다는 것만 빼면요. 벌점은 아래와 같이 구현해주면 됩니다.

\( s \color{orange}{ \xrightarrow{K} \text{ Penalty } \xrightarrow{K} } \text{ Worker } \xrightarrow{1} \text{ Work } \xrightarrow{1} t \)

 

즉, 벌점을 분배하는 정점을 따로 만들어주면 됩니다.

int adj[2020][2020], src, snk, nc;

int pth[2020], pc; bool chk[2020];
bool dfs(int now, int pos){
	chk[now] = 1; pth[pos] = now;
	if (now == snk){ pc = pos; return 1; }
	for (int nxt = 0; nxt < nc; nxt++){
		if (chk[nxt]){ continue; }
		if (adj[now][nxt] == 0){ continue; }
		if (dfs(nxt, pos+1)){ return 1; }
	}
	return 0;
}

void Main(){
	int n, m, k; cin >> n >> m >> k;
	src = 0; snk = n+m+1; nc = n+m+3;
	for (int i = 1; i <= n; i++){
		int p; cin >> p;
		while (p--){ int x; cin >> x; adj[i][x+n] = 1; }
	}
	adj[src][n+m+2] = k;
	for (int i = 1; i <= n; i++){ adj[src][i] = 1; adj[n+m+2][i] = k; }
	for (int i = 1; i <= m; i++){ adj[i+n][snk] = 1; }
	int ans = 0;
	while (dfs(src, 0)){
		memset(chk, 0, sizeof(chk));
		int res = 1e9;
		for (int i = 1; i <= pc; i++){
			//int v = pth[i-1], w = pth[i];
			res = min(res, adj[ pth[i-1] ][ pth[i] ]);
		}
		for (int i = 1; i <= pc; i++){
			//int v = pth[i-1], w = pth[i];
			adj[ pth[i-1] ][ pth[i] ] -= res; adj[ pth[i] ][ pth[i-1] ] += res;
		}
		ans += res;
	}
	cout << ans;
}

10. [1658] 돼지 잡기 (Platinum II)

우선 Source에서 각 우리로 \( A_{i} \)만큼의 간선을 놓고 시작합시다.

그 뒤로, 손님이 1명 올 때마다 \( A_{K_{1}}, A_{K_{2}}, A_{K_{3}}, \ldots, A_{K_{A}} \)에서 출발해서 새로운 정점 \( Qv_{j} \)에 모이는 간선을 만들어주면 됩니다. 모두 모일 수 있어야 하니 상한은 \( \infty \)입니다.

그리고 \( Qv_{j} \)에서는 Sink까지로 가는 상한이 \( B \)인 간선을 추가로 만들어주면 됩니다.

 

최종 답은 Source에서 Sink로 이동할 수 있는 돼지의 수, 즉 최대 유량입니다.

 

+ 설명은 저렇게 했지만, 실제로는 \( A_{K_{i}} \rightarrow Qv_{j} \)를 수행한 뒤에는 \( A_{K_{i}} \)를 \( Q_{v} \)로 바꿔야 합니다. 다르게 말하자면, 손님이 와서 문을 열 때마다 정점이 합쳐진다고 생각하면 됩니다.

const int INF = 1e9;
int adj[1120][1120], src, snk, nc;

int pth[1120], pc; bool chk[1120];
bool dfs(int now, int pos){
	chk[now] = 1; pth[pos] = now;
	if (now == snk){ pc = pos; return 1; }
	for (int nxt = 0; nxt < nc; nxt++){
		if (chk[nxt]){ continue; }
		if (adj[now][nxt] == 0){ continue; }
		if (dfs(nxt, pos+1)){ return 1; }
	}
	return 0;
}

int lst[1020];
void Main(){
	int n, m; cin >> n >> m;
	src = 0; snk = n+m+1; nc = n+m+2;
	for (int i = 1; i <= n; i++){ int x; cin >> x; adj[src][i] = x; lst[i] = i; }
	for (int i = 1; i <= m; i++){
		int k; cin >> k;
		while (k--){ int v; cin >> v; adj[ lst[v] ][n+i] = INF; lst[v] = n+i; }
		int x; cin >> x;
		adj[n+i][snk] = x;
	}
	int ans = 0;
	while (dfs(src, 0)){
		// cout << "PTH "; for (int i = 0; i <= pc; i++){ cout << pth[i] << ' '; } cout << endl;
		memset(chk, 0, sizeof(chk));
		int res = INF;
		for (int i = 1; i <= pc; i++){
			int v = pth[i-1], w = pth[i];
			res = min(res, adj[v][w]);
		}
		for (int i = 1; i <= pc; i++){
			int v = pth[i-1], w = pth[i];
			adj[v][w] -= res; adj[w][v] += res;
		}
		ans += res;
	}
	cout << ans;
}

11. [1031] 스타 대결 (Diamond V)

범위도 작고, 대진표는 1vs1 매칭이니 최대 유량을 써봅시다.

\( s \rightarrow i \rightarrow j \rightarrow t \)

간선의 상한은 \( s \rightarrow i \)와 \( j \rightarrow t \) 부분에서는 각 팀원이 해야 하는 대결의 수, 그리고 \( i \rightarrow j \)는 (최대 1회 대결 가능이므로) 1을 놓으면 됩니다.

 

이렇게 유량을 돌린 뒤, \( s \rightarrow i \) 또는 \( j \rightarrow t \)에서 꽉 차지 않은 간선이 남아있다면 대진표 작성이 불가능한 것이므로 -1을 출력해주면 됩니다.

 

하지만 가능하다고 해도, '사전순으로 가장 앞서는' 대진표를 만들어야 하기에 추가 작업이 필요합니다.

그러니, 대진표의 \( (1, 1) \)부터 시작해서 사전순 최소로 바꿔주는 작업을 해봅시다.

 

현재 대진표를 기준으로, \( (i, j) \)의 대결 여부를 생각해봅시다.

+ \( (i, j) \) 이전의 대결은 '이미 계산 후 고정'된 상태입니다.

만약 \( (i, j) \)가 0이라면, 굳이 힘들여서 1로 바꿀 필요가 없습니다. 어차피 앞이 고정되어있으니 1로 바꿔봤자 사전순으로 뒤쪽으로 가게 됩니다.

하지만 1이라면, 0으로 바꿀 여지가 남아있을 수도 있습니다. 그러니 \( s \rightarrow i \rightarrow j \rightarrow t \)로 흐르던 유량을 취소하고, \( (i, j) \)에 유량이 흐르지 않도록 고정한 뒤 그 상태에서 최대 유량을 구하면 됩니다.

만약 최대 유량이 유지가 되었다면 사전순으로 더 작은 대진표가 만들어졌으니 그대로 넘어가면 되고,

그렇지 않다면 불가능한 대진표가 되어버리니 \( (i, j) \)의 유량을 취소하기 전 상태로 되돌아가면 됩니다.

 

+ 그래서 고정은 어떻게 하나요?

그 간선에 유량이 흐른다 / 안 흐른다를 따로 저장한 뒤, 그 간선의 상한을 줄이면 됩니다.

 

최대 유량을 \( NM \)번 구하니 \( O(NM \times (N+M)^2 \cdot (N+M)^2) \)처럼 보이지만, 유량을 \( NM \)번 더 흘릴 때에는 사실 '추가 유량 1'만 흘려보면 되고, 이는 \( O(V+E) \)에 해결되므로 \( O( (N+M)^2 \cdot (N+M)^2 + NM \cdot (N+M)^2 )이 됩니다.

int n, m;
int sav[120][120], adj[120][120], src, snk, nc;

int pth[120], pc; bool chk[120];
int fxy, fxx;
bool dfs(int now, int pos){
	chk[now] = 1; pth[pos] = now;
	if (now == snk){ pc = pos; return 1; }
	for (int nxt = 0; nxt < nc; nxt++){
		int v = now, w = nxt;
		if (1 <= w && w <= n){ swap(v, w); }
		if (1 <= v && v <= n && n+1 <= w && w <= n+m){
			if (v < fxy || v == fxy && w <= n+fxx){ continue; }
		}
		if (chk[nxt]){ continue; }
		if (adj[now][nxt] == 0){ continue; }
		if (dfs(nxt, pos+1)){ return 1; }
	}
	return 0;
}

void Main(){
	cin >> n >> m;
	src = 0; snk = n+m+1; nc = n+m+2;
	int s1 = 0, s2 = 0;
	for (int i = 1; i <= n; i++){ int x; cin >> x; adj[src][i] = x; }
	for (int i = 1; i <= m; i++){ int x; cin >> x; adj[n+i][snk] = x; }
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){ adj[i][n+j] = 1; }
	}
	int ans = 0;
	while (dfs(src, 0)){
		memset(chk, 0, sizeof(chk));
		//cout << "PTH "; for (int i = 0; i <= pc; i++){ cout << pth[i] << ' '; } cout << endl;
		int res = 1;
		for (int i = 1; i <= pc; i++){
			int v = pth[i-1], w = pth[i];
			adj[v][w] -= res; adj[w][v] += res;
		}
		ans += res;
	}
	for (int i = 1; i <= n; i++){ if (adj[src][i] != 0){ cout << -1; return; } }
	for (int i = 1; i <= m; i++){ if (adj[n+i][snk] != 0){ cout << -1; return; } }
	for (int y = 1; y <= n; y++){
		for (int x = 1; x <= m; x++){
			if (adj[y][n+x] == 1){ continue; }
			for (int i = 0; i < nc; i++){ for (int j = 0; j < nc; j++){ sav[i][j] = adj[i][j]; } }
			adj[src][y] += 1; adj[y][n+x] += 1; adj[n+x][snk] += 1;
			adj[y][src] -= 1; adj[n+x][y] -= 1; adj[snk][n+x] -= 1;
			fxy = y; fxx = x;
			memset(chk, 0, sizeof(chk));
			if (dfs(src, 0)){
				int res = 1;
				for (int i = 1; i <= pc; i++){
					int v = pth[i-1], w = pth[i];
					adj[v][w] -= res; adj[w][v] += res;
				}
			}
			else{
				for (int i = 0; i < nc; i++){ for (int j = 0; j < nc; j++){ adj[i][j] = sav[i][j]; } }
			}
			/* cout << "RESULT " << y << ' ' << x << endl;
			for (int i = 0; i < nc; i++){
				for (int j = 0; j < nc; j++){ cout << adj[i][j]; }
				cout << endl;
			}
			cout << endl;
			cout << "ANSWER " << y << ' ' << x << endl;
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= m; j++){ cout << !adj[i][n+j]; }
				cout << endl;
			}
			cout << endl; */
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){ cout << !adj[i][n+j]; }
		cout << endl;
	}
}

12. [3692] 펭귄들의 행진 (Diamond V)

범위가 작으니 최대 유량을 의심해볼 수 있고, 정말 최대 유량이 맞습니다.

문제는 '펭귄이 얼음을 밟고 도약할 수 있는 횟수'인데, 이는 정점 분할을 통해 해결할 수 있습니다.

 

\( s \xrightarrow{n_{v}} v_{1} \xrightarrow{m_{v}} v_{2} \xrightarrow{\infty} w_{1} \xrightarrow{\infty} t \)

즉, 점프뛸 때 \( v_{1} \)에서 \( v_{2} \)로 이동시킨 뒤 점프를 뛰게 하면 됩니다.

물론 점프는 거리가 될 때만 뛸 수 있는데, 그냥 \( O(N^2) \)으로 거리 재주면 됩니다.

 

그런데 이 문제는 \( t \)를 고정하지 않습니다. 펭귄들이 모두 모일 수 있는 점을 하나하나 다 탐색해야 하므로, \( t \)와 연결되는 \( w_{1} \)이 바뀌게 됩니다. 그러므로 \( w_{1} \xrightarrow{\infty} t \) 부분을 모든 얼음에 대해 한 번씩 돌려보고, 흐르는 유량 (= 올 수 있는 펭귄의 수)가 펭귄의 총 수와 동일한지 하나하나 판별해주면 됩니다.

 

테스트케이스형 문제이기도 하고, \( E = O(V^2) \)이기도 하니 디닉을 써야 TLE 없이 맞을 수 있습니다.

const int INF = 1e9;
int sav[220][220], adj[220][220], src, snk, nc;
pi2 arr[120];

ll f(pi2 a, pi2 b){
	ll y = a.fr-b.fr, x = a.sc-b.sc;
	return y*y + x*x;
}

int ptr[220], dis[220];
void bfs(int st){
	for (int i = 0; i < nc; i++){ dis[i] = INF; ptr[i] = 0; }
	queue<pi2> q; q.push({st, 0}); dis[st] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc;
		q.pop();
		for (int nxt = 0; nxt < nc; nxt++){
			if (adj[now][nxt] == 0){ continue; }
			if (dis[nxt] != INF){ continue; }
			dis[nxt] = dst+1; q.push({nxt, dst+1});
		}
	}
}
bool chk[220]; int pth[220], pc;
bool dfs(int now, int idx){
	chk[now] = 1; pth[idx] = now;
	if (now == snk){ pc = idx; return 1; }
	for (int &nxt = ptr[now]; nxt < nc; nxt++){
		if (chk[nxt] || adj[now][nxt] == 0){ continue; }
		if (dis[now]+1 != dis[nxt]){ continue; }
		if (dfs(nxt, idx+1)){ return 1; }
	}
	return 0;
}

void Main(){
	int t; cin >> t;
	while (t--){
		int n; ld dd; cin >> n >> dd;
		ll d = dd*dd + eps;
		src = 0; nc = 2*n+1;
		int sum = 0;
		for (int i = 1; i <= n; i++){
			cin >> arr[i].fr >> arr[i].sc;
			int a, b; cin >> a >> b;
			sav[src][i*2-1] = a; sav[i*2-1][i*2] = b;
			sum += a;
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				if (i == j){ continue; }
				if (f(arr[i], arr[j]) <= d){ sav[i*2][j*2-1] = INF; }
			}
		}
		vector<int> anv;
		for (snk = 1; snk <= 2*n; snk+=2){
			//cout << "SNK " << snk << ' ' << snk/2 << endl;
			for (int i = 0; i < nc; i++){ for (int j = 0; j < nc; j++){ adj[i][j] = sav[i][j]; } }
			memset(chk, 0, sizeof(chk));
			int ans = 0;
			while (1){
				bfs(src); if (dis[snk] == INF){ break; }
				memset(chk, 0, sizeof(chk));
				while (dfs(src, 0)){
					int res = INF;
					for (int i = 1; i <= pc; i++){
						int v = pth[i-1], w = pth[i];
						res = min(res, adj[v][w]);
					}
					//cout << "PTH "; for (int i = 0; i <= pc; i++){ cout << pth[i] << ' '; } cout << "= " << res << endl;
					for (int i = 1; i <= pc; i++){
						int v = pth[i-1], w = pth[i];
						adj[v][w] -= res; adj[w][v] += res;
					}
					ans += res;
					memset(chk, 0, sizeof(chk));
				}
			}
			if (ans == sum){ anv.push_back(snk/2); }
		}
		for (int x : anv){ cout << x << ' '; }
		if (anv.empty()){ cout << -1; }
		cout << endl;
		memset(sav, 0, sizeof(sav));
	}
}