https://www.acmicpc.net/problem/1420

설명

우리는 최선을 다해서 학교 가는 것을 막아야 한다. 학교 가는 것을 막는 것은 일종의 그래프를 끊는 것으로 볼 수 있는데, 이러면 우리는 최대 유량 최소 컷 정리를 사용해야 한다.

이제 유량 그래프를 만들어 보자. 실제로 우리가 끊는 것은 각 칸의 간선이 아닌 정점 그 자체므로, 정점을 in과 out으로 분할하여 생각하면 된다. 한 정점 안의 in과 out에서는 용량이 1인 간선으로 연결하고, 다른 정점과 연결되는 간선에는 용량을 매우 크게 주면 된다.

이제 유량 그래프를 만들었다면, 실제 흐르는 최대 유량을 구할 차례이다. 그전에 유량의 시작점과 도착점이 딱 붙어있는지 확인하여 따로 처리를 해준다. 유량을 구할 때 나는 디닉을 사용하였다. 이 문제에서 문제점은 용량과 유량 배열을 미리 정해두면, 메모리 초과가 난다는 것이었다. 그래서 그냥 나는 std::map을 사용했다.

디닉에 대해서는 따로 설명은 하지 않겠다. 아무튼 디닉을 이용해서 최대 유량을 구하면 그것이 곧 그래프를 단절 시키는데 필요한 최소 비용이다. 잘 출력하자.

코드

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

constexpr int LEN = 20002;
constexpr int INF = 0x7FFFFFF;

vector<int> edge[LEN]; //간선
char label[101][101];

map<pii,int> C,F;

int level[LEN],work[LEN]; //레벨, 이미 탐색한 간선 알려줌.
int N,M,S,T; //시작점, 끝점.

bool Approx(int x,int y) {
    if(x>=0 && x<M && y>=0 && y<N) return true;
    return false;
}
bool Label() {
    memset(level,-1,sizeof(level));
    queue<int> task;
    task.push(S);
    level[S] = 0;
    while(!task.empty()) {
        int now = task.front();
        task.pop();
        for(int next : edge[now]) {
            if(level[next] == -1 && C[{now,next}]-F[{now,next}] > 0) {
                level[next] = level[now]+1;
                task.push(next);
            }
        }
    }
    if(level[T] == -1) return false;
    return true;
}
int DFS(int now,int flow) {
    if(now == T) return flow; 

    int sz = edge[now].size();
    for(int &i=work[now]; i<sz; i++) {
        int next = edge[now][i];
        if(level[next] == level[now]+1 && C[{now,next}]-F[{now,next}] > 0) {
            int amount = DFS(next,min(flow,C[{now,next}]-F[{now,next}]));
            if(amount > 0) {
                F[{now,next}] += amount;
                F[{next,now}] -= amount;
                return amount;
            }
        }
    }
    return 0;
}

//하나의 정점이 부여받은 idx에 대해, idx는 in idx+1는 out
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;

    int idx = -2;
    int sx,sy,tx,ty;
    for(int i=0; i<N; i++) for(int j=0; j<M; j++) {
        idx += 2;
        cin >> label[j][i];
        if(label[j][i] == '#') continue;
        if(label[j][i] == 'K') S = idx+1, sx = j, sy = i;
        else if(label[j][i] == 'H') T = idx, tx = j, ty = i;

        edge[idx].push_back(idx+1);
        edge[idx+1].push_back(idx);
        C[{idx,idx+1}] = 1;

        if(Approx(j-1,i) && label[j-1][i] != '#') {
            edge[idx+1].push_back(idx-2);
            edge[idx-2].push_back(idx+1);
            C[{idx+1,idx-2}] = INF;

            edge[idx-1].push_back(idx);
            edge[idx].push_back(idx-1);
            C[{idx-1,idx}] = INF;
        }
        if(Approx(j,i-1) && label[j][i-1] != '#') {
            edge[idx+1].push_back(idx-2*M);
            edge[idx-2*M].push_back(idx+1);
            C[{idx+1,idx-2*M}] = INF;

            edge[idx-2*M+1].push_back(idx);
            edge[idx].push_back(idx-2*M+1);
            C[{idx-2*M+1,idx}] = INF;
        }
    }
    if(abs(sx-tx)+abs(sy-ty) == 1) cout << -1, exit(0);

    int ans = 0;
    while(Label()) {
        memset(work,0,sizeof(work));
        int flow = DFS(S,INF);
        while(flow != 0) {
            ans += flow;
            flow = DFS(S,INF);
        }
    }
    cout << ans;
    exit(0);
}

여담

확실히 유량 쪽이 어렵다. 이게 유량인지 잘 보이지도 않는다.