문제 출처 :
https://www.acmicpc.net/problem/7616
알고리즘 분석 :
문제 해결에 필요한 사항
1. 네트워크 플로우 :: http://www.crocus.co.kr/741
2. 최대 유량
[2316번] 도시 왕복하기 :: http://www.crocus.co.kr/742 문제를 꼭 풀고 이 문제를 접했으면 좋겠다.
이 문제는 위의 문제의 상위 버전이므로, 위의 내용을 이해한다면 이 문제도 풀 수 있다.
이 문제를 풀면서 엄청 많은 WA를 받았고, 결국 최종적으로 AC를 받게 되었다.
문제 입력부터 이해가 잘 안되는 부분이 많았다.
그리고 나중에 테스트 케이스를 어떡하다보니 얻게되어 돌려보니, 겹치지 않는 경로가 K개 이상이 있는 경우가 존재했다.
따라서 K개 이상이어도 K개만 출력하도록 해야하는데 그 부분에서 계속 틀리고 있었다.
입력 부분부터 심상치가 않다.
입력 부분은 already와 chk부분이 없어도 된다. 하지만 없으면 adj 벡터에 계속해서 같은 값이 들어갈 수 있다.
예를들어 첫번째 테스트 케이스가 아래와 같이 생겼지만
3 5 3 4 5 3 4 5 1 2 1 2 1 2
3 5 3 3 3 3 3 3 3 3 3 4 4 4 4 4 5 3 4 3 3 3 3 3 4 5 3 3 4 5 5 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 2 1 2 1 1 2 2
이렇게도 들어올 수 있기에 이러한 과정을 방지해주기 위해 already와 chk배열을 두었다.
그 아래는 에드몬드 카프 알고리즘을 통해 최대 유량을 확인하는데 memcpy를 통해 visit의 방문 누적을 계속 갱신해주고 있다.
(이 과정은 위의 도시 왕복하기에 링크를 통해 들어가보면 visit에 대한 설명이 있다.)
그리고 아래에는
f[prev[i]][i] = 1;
f[i][prev[i]] = 0;인데 이 부분은 어짜피 용량이 최대 1이고, 유량은 1또는 0이기에
에드몬드 카프 알고리즘에서 최소 flow를 찾는 과정을 없애고 다음과 같이 그냥 표시하였다.
마지막으로 totalFlow >= n을 통해 K개 이상의 이동가능한 flow가 있어도 K개만 표시하도록 나타내었다.
소스 코드 :
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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | #include <iostream> #include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <memory.h> #include <string.h> #include <stack> #define MAX 5001 #define INF 987654321 using namespace std; // 모든 배열은 용량이 1이기에 bool로 선언 가능 // 그리고, 한번만 방문하기에 c, f배열이 2가 될 수 없음 // 무조건 0 또는 1 bool c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량 bool f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량 bool visit[MAX]; // 방문 배열 bool tmp[MAX]; // 방문 배열 복사 bool already[MAX]; // 메모이제이션을 위한 배열 bool chk[MAX]; // 메모이제이션을 위한 배열 int main() { int n, p, tCase = 1; while (1) { memset(c, 0, sizeof(c)); memset(f, 0, sizeof(f)); memset(visit, false, sizeof(visit)); memset(tmp, false, sizeof(tmp)); memset(already, false, sizeof(already)); stack<int> st; vector<int> adj[MAX]; // 입력 scanf("%d %d", &n, &p); if (n == 0 && p == 0) break; for (int i = 1; i <= p; i++) { // adj 벡터에 중복 입력을 막기위해 이용 memset(chk, false, sizeof(chk)); while (1) { int to; char ch; scanf("%d%c", &to,&ch); // i에 의해 to에도 이미 값이 들어간다면 중복이기에 // 나중에 to가 i가될 때 to에서 i로 값이 들어오는것을 방지 if(!already[i]) already[i] = true; if (!already[to]) { // to에 이미 값이 한번 들어왔다면 // 그 값으로 인해 i와 to는 또 중복이 생기는 것을 방지 if (!chk[to]) { chk[to] = true; c[i][to] = 1; c[to][i] = 1; adj[i].push_back(to); adj[to].push_back(i); } } if (ch == '\n') break; } } int totalFlow = 0, S = 1, T = 2; // S :: source, T :: sink // 증가 경로를 못 찾을 때까지 while (1) { int prev[MAX]; memset(prev, -1, sizeof(prev)); queue<int> q; // 싱크를 처음 push 해준다. q.push(S); while (!q.empty()) { int cur = q.front(); q.pop(); if (cur != S && cur != T) visit[cur] = true; for (int i = 0; i < adj[cur].size(); i++) { int next = adj[cur][i]; // next를 방문하였다면 continue if (prev[next] != -1 || next == S) continue; // 아직 흐를 수 있는 유량이 있다면 // 즉, cur -> next로 갈 수 있는 유량이 있다면 if (!visit[next] && c[cur][next] - f[cur][next] > 0) { q.push(next); // next의 경로 추적을 위해 저장 prev[next] = cur; // 만약 next가 sink면 break if (next == T) break; } } } memset(visit, false, sizeof(visit)); // source -> sink의 간선이 없다면 break; if (prev[T] == -1) break; // 해당 경로에 flow를 보낸다. // 그리고 역방향으로는 flow를 빼준다. // memcpy를 통해 방문 위치를 계속해서 기록해둔다.(중복 방문 방지) memcpy(visit, tmp, sizeof(tmp)); for (int i = T; i != S; i = prev[i]) { st.push(i); f[prev[i]][i] = 1; f[i][prev[i]] = 0; if (i != S && i != T) visit[i] = true; } memcpy(tmp, visit, sizeof(visit)); st.push(1); totalFlow ++; } printf("Case %d:\n", tCase++); // n개만 출력(n개 이상의 경로가 있어도) if (totalFlow >= n) { while (!st.empty() && n) { printf("%d ", st.top()); if (st.top() == 2) { n--; printf("\n"); } st.pop(); } } else printf("Impossible\n"); printf("\n"); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1420번] 학교 가지마! (0) | 2017.04.11 |
---|---|
[1733번] 등번호 (0) | 2017.04.10 |
[2316번] 도시 왕복하기 (4) | 2017.04.08 |
[9373번] 복도 뚫기 (0) | 2017.04.07 |
[1793번] 타일링 (0) | 2017.04.07 |