BOJ 3640. 제독 ) MCMF - SPFA

제독 문제 바로가기

제독 문제를 살펴보면, 

배가 출항을 하는데 있어서 중간 지점들 ($W_1, W_2, ... , W_N$) 사이의 뱃길들을 건너야 한다.

문제는 뱃길들을 건너려면 적들의 공세를 받아쳐야 하는데 각각 공세를 받아치는 데에 필요한 포탄 갯수가 뱃길 사이에 있다.

문제는 제독에서는 두 전함을 출항시키는 데, 두 전함은 출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안된다.

여기서 알 수 있는 점은, 2개의 flow를 흘려내보내면서 minimum한 경로로 흘려보내야 하는 MCMF임을 주의하면 된다. 단, 같은 뱃길을 지나면 안된다에서 한 가지 유의할 점이 있는데,

이는

각 중간 지점 $W_1, W_2, ... , W_N$ 마다 $(W^s_1, W^e_1, W^s_2, W^e_2, ... )$와 같은 start와 end vertex를 만든후 start -> end vertext 간 capacity를 1로 해주면 해결이 된다.

아래는 예시 코드이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

#include <stdio.h> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <map> #define INF 999999999 using namespace std;   map< pair<int, int> , int > c; map< pair<int, int> , int > f; map< pair<int, int> , int > d;   int dist[2020]; int p[2020]; bool inQ[2020];   vector<int> adj[2020];   int v, e;   int S = 0, E = 2010;   pair<int, int> SPFA(){     int flow = 0;     int cost = 0;          while(1) {         for(int i=0; i<2020; i++) {             dist[i] = INF;             p[i] = -1;             inQ[i] = 0;         }         queue<int> q;         q.push(S);         dist[0] = 0;         while(!q.empty()) {             int cur = q.front(); q.pop();             inQ[cur] = 0;             for(auto next : adj[cur]) {                 if(c[{cur,next}] > f[{cur,next}] && dist[next] > dist[cur]+d[{cur,next}]){                     dist[next] = dist[cur] + d[{cur, next}];                     p[next] = cur;                     if(!inQ[next]){                         q.push(next);                         inQ[next] = 1;                     }                 }             }         }                  if(p[E] == -1) break;           int cur_flow = 999999999;                  for(int i = E; i != S; i = p[i]){             cur_flow = min(cur_flow, c[{p[i], i}] - f[{p[i], i}]);         }                  flow += cur_flow;           for(int i = E; i != S; i = p[i]){             //printf("cur: %d\n", i);             //printf("(%d, %d) d: %d\n", p[i]/2, i/2, d[{p[i], i}]);             cost += d[{p[i], i}] * cur_flow;             f[{p[i], i}] += cur_flow;             f[{i, p[i]}] -= cur_flow;         }     }     return {cost, flow}; }   int main(){     while(scanf("%d %d", &v, &e) != EOF){         c.clear();         f.clear();         d.clear();         for(int i=0; i<2020; i++) adj[i].clear();                  int a, b, V;         for(int i=0; i<e; i++){             scanf("%d%d%d", &a, &b, &V);             adj[2*a+1].push_back(2*b);             adj[2*b].push_back(2*a+1);             adj[2*b+1].push_back(2*a);             adj[2*a].push_back(2*b+1);             c[{2*a+1, 2*b}] = 1;             d[{2*a+1, 2*b}] = V;             d[{2*b, 2*a+1}] = -V;         }                  for(int i=1; i<=v; i++){             adj[2*i].push_back(2*i+1);             adj[2*i+1].push_back(2*i);             c[{2*i, 2*i+1}] = 1;         }         c[{2, 3}] = 2;         c[{2*v, 2*v+1}] = 2;                  c[{S, 2}] = 2;         c[{2*v+1, E}] = 2;                  adj[0].push_back(2);         adj[2*v+1].push_back(E);                  pair<int, int> p = SPFA();         printf("%d\n", p.first);     } } Colored by Color Scripter

cs

이를 해결하기 위해 SPFA라는 알고리즘을 사용하였다. 흔히 음수 경로에서 나타나는 최단 경로를 해결하기 위한 알고리즘으로 잘 알려져있다.

먼저 흘려보낼 수 있는 flow와 cost를 초기화한다. (line 25, 26)

이후 flow를 찾을 때마다 dist, parent, inQ를 초기화 한다. (line 29~33)

SPFA의 핵심 아이디어는 start vertex에서 출발할 때마다 

다음 vertex로 넘어갈 remain flow가 남아있고, 해당 길로 통한 거리가 현재 기록된 거리보다 짧으면

q에다가 집어넣는다.

그리고 해당 vertex의 parent를 설정한다.

여기서 주의할 점은 중복 확인을 없애기 위해 inQ를 도입하여 queue에 있는지 없는지를 확인한다.

parent를 이용하면 각 길을 통한 최소의 remain flow를 알 수 있는데 이를 추적하여 cost를 구해줄 수 있다.

만약, 최대값을 구해야한다면 마이너스 부호를 붙여 MCMF로 해결할 수 있다.