https://www.acmicpc.net/problem/6086
네트워크 플로우에서 최대 유량 문제입니다.
저도 처음 공부하기 때문에 다른 블로그를 참조하면서 공부했습니다.
필요한 변수 선언입니다.
| int n; //input으로 받는 edge 수 vector<int> adj[MAX_SIZE]; // 인접 int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량 int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양 int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지) | cs |
입력 부분입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | //입력 scanf("%d", &n); getchar(); for (int i = 0; i < n; i++) { char s, e; int c; scanf("%c %c %d", &s, &e, &c); getchar(); s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환 //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨 capacity[s][e] += c; //정,역방향 간선 추가 adj[s].push_back(e); adj[e].push_back(s); } | cs |
15번째 줄의 += 부분이 잘이해가 안가실 수 있습니다.
capacity배열은 0으로 전부 초기화 되어있습니다.
입력에서 만약 A -> B 로 가는 edge를 여러개로 준다면
A->B로 가는 유량은 edge의 총 용량만큼이기 때문에 +=로 해주는 것입니다.
19번째에서 역방향 간선까지 추가하는 것이 포드 풀커슨 알고리즘의 핵심인 것 같습니다..(잘은 이해안감..ㅠㅠ)
처리부분입니다.
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 | //process int total_flow = 0; const int start = ctoi('A'), end = ctoi('Z'); while (1) { for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1; queue<int> q; q.push(start); while (!q.empty()) { int curr = q.front(); q.pop(); for (int i = 0; i < adj[curr].size(); i++) { int next = adj[curr][i]; if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) { q.push(next); prev[next] = curr; if (next == end) break; } } } if (prev[end] == -1) break; //Z까지 가는 길이 없으면.. //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택 int min_flow = INF; for (int i = end; i != start; i = prev[i]) min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]); //A에서 Z로 가는 경로에 물을 흘림 //지나간 경로의 반대 경로에는 -값의 물을 흘림 for (int i = end; i != start; i = prev[i]) { flow[prev[i]][i] += min_flow; flow[i][prev[i]] -= min_flow; } total_flow += min_flow; } | cs |
start, end는 시작과 끝점 입니다. 이 문제에서는 'A'와 'Z'가 되겠습니다.
bfs를 통해서 A->Z로 가는 경로를 찾습니다.
경로는 prev배열에 현재 정점 바로 전의 정점을 저장을 해서 경로를 알 수 있습니다.
예를 들어 A->B->C 라면 prev[A] = -1, prev[B] = A, prev[C] = B 입니다.
최종 도착지점은 항상 'Z'이므로 Z부터 역으로 추적하면 A까지 도달할 수 있습니다.
16번째 줄이 굉장히 중요합니다.
| for (int i = 0; i < adj[curr].size(); i++) { int next = adj[curr][i]; if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) { q.push(next); prev[next] = curr; if (next == end) break; } } | cs |
curr(현재 정점)에서 연결되어 있는 부분을 탐색합니다.
curr->next의 edge에 용량이 꽉 차지 않았다면 그리고 아직 방문하지 않았다면
if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1)
next 정점을 q에 넣고 prev[다음 정점] = 현재 정점 을 넣어줍니다.
만약 다음 정점이 'Z'(end)라면 루프를 빠져나옵니다.
| if (prev[end] == -1) break; //Z까지 가는 길이 없으면.. //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택 int min_flow = INF; for (int i = end; i != start; i = prev[i]) min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]); //A에서 Z로 가는 경로에 물을 흘림 //지나간 경로의 반대 경로에는 -값의 물을 흘림 for (int i = end; i != start; i = prev[i]) { flow[prev[i]][i] += min_flow; flow[i][prev[i]] -= min_flow; } total_flow += min_flow; | cs |
주석을 달아 놓은 것처럼
1번째 줄은 정점 'Z'(end)의 이전 정점이 -1라는 것은 bfs에서 Z로 도달하지 못했음을 의미합니다.
그렇기 때문에 더이상 경로가 없음을 의미해서 break;합니다.
그게 아니라면 4번째 줄
bfs로 찾은 경로 구간 중에서 가장 용량이 작은 구간을 선택합니다.
유량을 가장 작은 용량으로 맞춰야만 그 경로로 흘릴 수 있기 때문입니다.
만약 이전 bfs에서 유량이 있을 수 있으므로 최소 용량은 capacity[이전 정점][현재 정점] - flow[이전 정점][현재 정점]으로 구해야 합니다.
그리고
10번째 줄에서 A->Z까지의 경로에 위에서 찾은 min_flow(가장 작은 유량)을 더합니다.
여기서 중요한 부분은 12번째 줄입니다. 경로의 반대 방향으로 -유량을 더해줍니다.
위의 input부분에서 역방향 간선까지 함께 만든 이유입니다.
capacity[curr][next] - flow[curr][next] > 0
아까 이 부분에서 0보다 크면 큐에다가 next를 푸시했는데요.
만약 flow[curr][next]가 -유량이라면 +가 되기 때문에 항상 흐를 수 있습니다.
예시를 보면서 이해하도록 하겠습니다.
이 예시는
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235
를 참고 했으며 제가 설명하는 것 보다 훨씬 상세하게 설명해주셨습니다. 저도 이 블로그를 보고 이해했습니다.
지저분해도 .. 이해해주세요!
bfs로
이 경로까지는 찾으셨을텐데요..
이 유량을 다합치면 9가 되죠.
이게 최대일 것 같지만 그렇지 않습니다.
A->E->F->D->B->G->Z의 경로로 1만큼 흘린다면 Z에 최대 10까지 도달할 수 있습니다.
저는 여기서 D->B구간이 이해가 안갔는데..
이 부분이 -유량을 흘린 이유입니다.
B->D구간의 유량은 3이 흐르고 있습니다.
D->B구간은 애초에 경로가 없습니다. 어떻게 흐를까요?
사실.. 진짜로 흐르는 것이 아니라 B->D구간을 상쇄시키는 느낌??적인 느낌입니다.
D->B구간으로 1을 흘려보내면 B->D구간에서 원래 3이 흐르고 있었으니.. 2가 되겠죠!
그리고 그 B->D에서 상쇄시킨 그 1을 B->G 구간으로 보내는 것입니다!!!!!....
느낌만 이해했습니다.. 완전 이해는 아닌..
어떻게 이런거 까지 생각해냈는지는 잘 모르겠네요...ㅠㅠㅠ
제가 참고하라고 올려드린 블로그..
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235
를 참조해주세요!!!!!! 정말 잘 설명해주셨습니다..
아래는 풀 코드입니다.
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 | /* input) 11 A B 3 A C 3 A D 4 B E 2 C B 10 C E 1 D F 5 E D 1 E F 1 E Z 2 F Z 5 output) 7 */ #include <cstdio> #include <iostream> #include <vector> #include <queue> #define MAX_SIZE 52 #define INF 0x7fffffff using namespace std; int ctoi(char c) { if (c <= 'Z') return c - 'A'; return c - 'a' + 26; } int main() { int n; vector<int> adj[MAX_SIZE]; // 인접 int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량 int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양 int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지) //입력 scanf("%d", &n); getchar(); for (int i = 0; i < n; i++) { char s, e; int c; scanf("%c %c %d", &s, &e, &c); getchar(); s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환 //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨 capacity[s][e] += c; //정,역방향 간선 추가 adj[s].push_back(e); adj[e].push_back(s); } //process int total_flow = 0; const int start = ctoi('A'), end = ctoi('Z'); while (1) { for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1; queue<int> q; q.push(start); while (!q.empty()) { int curr = q.front(); q.pop(); if (curr == end) break; for (int i = 0; i < adj[curr].size(); i++) { int next = adj[curr][i]; if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) { q.push(next); prev[next] = curr; } } } if (prev[end] == -1) break; //Z까지 가는 길이 없으면.. //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택 int min_flow = INF; for (int i = end; i != start; i = prev[i]) min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]); //A에서 Z로 가는 경로에 물을 흘림 //지나간 경로의 반대 경로에는 -값의 물을 흘림 for (int i = end; i != start; i = prev[i]) { flow[prev[i]][i] += min_flow; flow[i][prev[i]] -= min_flow; } total_flow += min_flow; } printf("%d\n", total_flow); return 0; } | cs |
