[백준] 3073 집으로 가는 길

문제

격자로 된 지도에 n명의 어린이와 n개의 집이 있다. 각각의 단위 시간동안, 모든 어린이가 한 단위만큼 움직일 수 있다. (수평이나 수직의 인접한 점으로) 당신은 각각의 어린이가 집에 들어갈 때까지, 1번 움직일 때마다 1달러의 여행비를 지불해야한다. 각각의 집에는 오직 한 명의 어린이만 들어갈 수 있다. 

당신의 목표는 n명의 어린이들을 n개의 다른 집으로 보내는데 지불해야하는 비용을 최소화 하는 것이다. 입력은 지도인데, '.' 은 빈 공간을 의미하고 'H'는 집을 의미하고 'm' 은 어린이를 의미한다.

격자로 된 지도에서 각각의 점을 격자라고 간주한다. 그리고 이 격자에 n명의 어린이를 동시에 놓을 수 있다. 또한, 한 어린이가 집으로 들어가지 않고 집의 격자로 움직이는 것은 가능하다.

입력

입력으로 하나에서 여러 개의 테스트 케이스가 있다. 각각의 케이스의 첫 줄은 N과 M의 두개의 정수이다. N은 지도의 행(row)의 개수이고, M은 지도의 열(column)의 개수이다. 입력의 나머지는 N개의 줄 지도를 묘사한다. N와 M은 둘다 2~100 사이로 가정한다. 지도에서 'H'와 'm'의 개수는 같다. 그리고 최대 100개의 집이 있을 수 있다.

N과 M 을 0 0 으로 입력하면 입력이 종료된다.

출력

각각의 테스트 케이스에서 출력의 첫 줄은 하나의 정수이다. 그것은 지불해야할 최소한의 달러의 양이다.

 

각 좌표에서 모든 어린이들이 집에 각각 하나씩 매칭되어 들어가야합니다.

이때, 한 격자씩 움직일 때마다 비용은 1달러인데, 모든 어린이들이 집을 가는데 최소비용을 구해야합니다.

MCMF문제입니다.

SPFA알고리즘을 사용합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

struct Edge {
    int t;
    int c;
    int f = 0;
    int cost = 0;
    Edge* rev;

    Edge(int to, int capacity,int costs) {
        t = to;
        c = capacity;
        cost = costs;
    }
    int R() {
        return c - f;
    }
    void F(int amount) {
        f += amount;
        rev->f -= amount;
    }
};
int n, m, S = 10001, E = 10002;
vector<Edge*>adj[10004];
void AddEdge(int f, int t, int c,int costs) {

    Edge* e = new Edge(t, c, costs);
    Edge* rev = new Edge(f, 0 ,-costs);

    e->rev = rev;
    rev->rev = e;

    adj[f].push_back(e);
    adj[t].push_back(rev);
}
int main() {
    FAST;
    while (cin >> n >> m) {
        rep(i, 10004)adj[i].clear();
        int ans = 0;
        int cnt = 0;
        if (n == 0 && m == 0)break;
        rep(i, n) {
            rep(j, m) {
                char c;
                cin >> c;
                if (c == 'm') {
                    cnt++;
                    int f = S;
                    int t = i * m + j;
                    Edge* e = new Edge(t, 1 , 0);
                    Edge* rev = new Edge(f, 0 , 0);

                    e->rev = rev;
                    rev->rev = rev;

                    adj[f].push_back(e);
                    adj[t].push_back(rev);
                }
                else if (c == 'H') {
                    int f = i * m + j;
                    int t = E;
                    Edge* e = new Edge(t, 1 , 0);
                    Edge* rev = new Edge(f, 0, 0);

                    e->rev = rev;
                    rev->rev = rev;

                    adj[f].push_back(e);
                    adj[t].push_back(rev);

                }
                rep(k, 4) {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                        AddEdge(i * m + j, ny * m + nx, INF,1);
                    }
                }
            }
        }
        while(1){
            queue<int>q;
            int inQ[10004];
            int dist[10004];
            int p[10004];
            Edge* FromEdge[10004];
            memset(p, -1, sizeof(p));
            memset(dist, 0x7f, sizeof(dist));
            mset(inQ);
            q.push(S);
            dist[S] = 0;
            inQ[S] = 1;
            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                inQ[cur] = 0;
                for (auto e : adj[cur]) {
                    int to = e->t;
                    if (dist[to] > dist[cur] + e->cost && e->R() > 0) {
                        p[to] = cur;
                        dist[to] = dist[cur] + e->cost;
                        FromEdge[to] = e;
                        if (!inQ[to]) {
                            inQ[to] = 1;
                            q.push(to);
                        }
                    }
                }
            }
            if (p[E] == -1)break;
            for (int i = E; i != S; i = p[i]) {
                Edge* e = FromEdge[i];
                e->F(1);
                ans += e->cost;
            }
        }
        cout << ans << "\n";
    }
}

정점의 개수가 10000개이므로, 배열로 간선의 capacity와 flow를 저장할 수 없습니다.

따라서 간선 struct를 선언합니다.

 

 

이 문제가 까다로웠던점은,,,,

 1.격자좌표이므로 각 정점의 위치는 i * m + j 번 입니다.

 2.간선은 양방향입니다. 양방향 간선을 표현하는데 역방향 간선을 포함하지 않습니다. 이는 A정점과 B정점이 총 4개의 간선으로 연결되어있다는 것입니다.

    1. A->B : capacity = 1 , cost = 1

    2. A->B rev:capacity = 0, cost = -1

    3. B->A : capacity =1 , cost = 1

    4. B->A rev: capacity=0 , cost = -1

 

역방향 간선의 capacity 는 0이고 cost는 - 입니다.

3.SFPA 알고리즘을 사용할때 배열 p와 FromEdge를 사용합니다.

 p[x]는 x의 부모 노드를 저장합니다.

 FromEdge[x]는 x로 향하는 간선을 저장합니다.