BOJ 1420: 학교 가지마! 작성일 2020-03-07 https://www.acmicpc.net/problem/1420 3월동안 210문제 풀기 (15/210) 디닉 연습용 Network Flow문제 지난번에 배운 것처럼, 노드에 상한이 있을 경우 Source와 Sink를 노드 안에 만드는 식으로 해결 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = 1e9; struct Edge { int v; LL cap, flow = 0; Edge* back; }; struct Dinic { int N, S, T; vector<vector<Edge*>> adj; vector<int> ptr, level; queue<int> q; Dinic(int n): N(n) { adj.resize(n); ptr.resize(n); level.resize(n); } void addEdge(int u, int v, LL cap) { Edge* fe = new Edge({v, cap}); Edge* be = new Edge({u, 0}); fe->back = be, be->back = fe; adj[u].push_back(fe); adj[v].push_back(be); } bool bfs() { fill(level.begin(), level.end(), 0); q.push(S); level[S] = 1; while(q.size()) { int u = q.front(); q.pop(); for(Edge* e : adj[u]) { if(level[e->v] || e->cap - e->flow == 0) continue; level[e->v] = level[u] + 1; q.push(e->v); } } return level[T] != 0; } LL dfs(int u, LL pushed) { if(u == T || !pushed) return pushed; for(int& i = ptr[u]; i < adj[u].size(); i++) { Edge* e = adj[u][i]; if(level[u]+1 != level[e->v]) continue; if(e->cap - e->flow == 0) continue; LL flew = dfs(e->v, min(e->cap-e->flow, pushed)); if (flew == 0) continue; e->flow += flew; e->back->flow -= flew; return flew; } return 0; } LL maxFlow() { LL ret = 0; while(bfs()) { fill(ptr.begin(), ptr.end(), 0); while(LL pushed = dfs(S, INF)) ret += pushed; } return ret; } }; int N, M; inline int GS(int x, int y) { return x*2*M + 2*y; } inline int GT(int x, int y) { return x*2*M + 2*y+1; } inline bool bound(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; } const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0}; vector<string> arr; void fillEdge(Dinic& graph, int x, int y) { if(arr[x][y] != '#') graph.addEdge(GS(x,y), GT(x,y), 1); if(arr[x][y] == '.' || arr[x][y] == 'K') { for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!bound(nx,ny)) continue; graph.addEdge(GT(x,y), GS(nx,ny), INF); } } if(arr[x][y] == 'K') graph.S = GT(x,y); if(arr[x][y] == 'H') graph.T = GS(x,y); } int main() { ios::sync_with_stdio(false); cin >> N >> M; arr.resize(N); for(int i = 0; i < N; i++) cin >> arr[i]; Dinic graph(2*N*M); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) fillEdge(graph,i,j); LL flow = graph.maxFlow(); cout << (flow >= 1e9 ? -1 : flow); }