[BOJ 2316]
문제 바로가기 : https://www.acmicpc.net/problem/2316
문제 설명은 위 링크에서 확인해주시길 바랍니다.
solutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //2316 | |
| #include <iostream> | |
| #include <string> | |
| #include <cstring> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <queue> | |
| #include <algorithm> | |
| using namespace std; | |
| #define INF 987654321 | |
| #define MAX 876 | |
| #define OUT 400 | |
| typedef long long ll; | |
| typedef vector<int> vi; | |
| int ret; | |
| int cap[MAX][MAX], flo[MAX][MAX], from[MAX]; | |
| vi node[MAX]; | |
| void networkFlow(int start, int end) { | |
| while (1) { | |
| fill(from, from + MAX, -1); | |
| queue<int> q; | |
| q.push(start); | |
| while (!q.empty()) { | |
| int cur = q.front(); | |
| q.pop(); | |
| for (auto& next : node[cur]) { | |
| //cout << "cur:" << cur << " next:" << next << '\n'; | |
| if (cap[cur][next] - flo[cur][next] > 0 && from[next] == -1) { | |
| from[next] = cur; | |
| q.push(next); | |
| if (next == end) break; | |
| } | |
| } | |
| } | |
| if (from[end] == -1) break; | |
| int flow = INF; | |
| for (int i = end; i != start; i = from[i]) { | |
| flow = min(flow, cap[from[i]][i] - flo[from[i]][i]); | |
| } | |
| for (int i = end; i != start; i = from[i]) { | |
| //cout << "i:" << i << '\n'; | |
| flo[from[i]][i] += flow; | |
| flo[i][from[i]] -= flow; | |
| } | |
| ret += flow; | |
| } | |
| } | |
| int main() { | |
| cin.tie(nullptr); | |
| cout.tie(NULL); | |
| ios_base::sync_with_stdio(false); | |
| //input | |
| int n, p; cin >> n >> p; | |
| for (int i = 0; i < p; i++) { | |
| int a, b; cin >> a >> b; | |
| node[a + OUT].push_back(b); | |
| node[b].push_back(a + OUT); | |
| node[b + OUT].push_back(a); | |
| node[a].push_back(b + OUT); | |
| cap[a + OUT][b] = 1; | |
| cap[b + OUT][a] = 1; | |
| } | |
| //in -> out | |
| for (int i = 3; i <= n; i++) { | |
| node[i].push_back(i + OUT); | |
| cap[i][i + OUT] = 1; | |
| } | |
| networkFlow(1+OUT, 2); | |
| cout << ret; | |
| return 0; | |
| } |
reviewPermalink
BOJ 17412: 도시 왕복하기 1에서 몇 가지 옵션이 추가됐다.
중복해서 지나가지 않아야 하며, 단방향 길이 아닌 양방향 길로 연결된다는 점이다.
쓰이는 알고리즘은 같다. 하지만 알고리즘을 쓰기 전에 약간의 수정이 필요하다. 그림으로 나타내면 다음과 같다.
노드안에 또 다른 노드 2개를 설정해놓고 이 노드들 사이의 용량을 1로 설정해주면 중복해서 지나가지 않는다.
이해를 돕고자 또 다른 노드 2개를 설정한다고 했지만 사실은 원래 노드 옆에 1개를 더 추가해주는 셈이다.
IN이 원래 노드여서 인덱스가 i라면 OUT의 인덱스는 i+OUT이 된다!
a와 b가 연결됐다면 a+OUT이 b를, b+OUT이 a를 가르켜야 한다.
또 내부적으로는 a->a+OUT, b->b+OUT이 있어야 한다. 이 때 용량은 1로 설정해주자.
물론 길이라고만 했고 별도의 용량은 주어지지 않았으므로 a와 b사이 간선의 용량은 1이다.
//input
int n, p; cin >> n >> p;
for (int i = 0; i < p; i++) {
int a, b; cin >> a >> b;
node[a + OUT].push_back(b);
node[b].push_back(a + OUT);
node[b + OUT].push_back(a);
node[a].push_back(b + OUT);
cap[a + OUT][b] = 1;
cap[b + OUT][a] = 1;
}
//in -> out
for (int i = 3; i <= n; i++) {
node[i].push_back(i + OUT);
cap[i][i + OUT] = 1;
}
주의해야할 점은, 1->2 경로 상에서 값을 구해야하기 때문에 1은 1+OUT부터 시작한다.
따라서 다음과 같이 처리해줘야 한다.
networkFlow(1+OUT, 2); //start = 1+OUT
cout << ret;
댓글남기기