🧺입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.
🧺출력
첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다.
🔮예제 입력1
5 5 1 3 3 2 1 5 5 4 4 2
🔮예제 출력1
2
🔮예제 입력2
6 7 1 3 3 2 1 4 4 2 1 5 5 6 6 2
🔮예제 출력2
3
🔮예제 입력3
7 8 1 3 1 4 3 5 4 5 5 6 5 7 6 2 7 2
🔮예제 출력3
1
최대 유량, 네트워크 유량, 분할 정복
플래티넘III
우선은 이 문제는 네트워크유량과 분할정복을 사용하여 풀수있습니다.
네트워크유량 알고리즘함수쪽은 전혀건드리지않았구요, 이 문제에서는 분할 정복이라는것이 사용됩니다.
한 정점내에 다른정점으로부터 연결되오는 in과 다른정점으로 연결하는 out으로 정점을 분할하여 풀수있습니다.
우선은 in은 1~401까지 out은 402~801까지로 설정했습니다.
우선 1부터 N만큼의 정점이 존재합니다.
따라서, 정점의 갯수인 1부터 N의 정점들을 모두 in, out정점으로 분할하여 서로를 가리키도록하며, 이때 용량은 1이됩니다.
그리고 언제나 out정점이 in정점을 가리켜야하므로,
{a의 out} -> {b의 in}, {b의 in} -> {a의 out}
{b의 out} -> {a의 in}, {a의 in} -> {b의 out}
이런식으로 가리켜야하며, 이때 용량은 양방향으로 모두 1로 설정합니다.
마지막으로 시작지점은 1이아닌 OUT + 1이됩니다.
마찬가지로 현재 정점의 out이 다른정점의 in을 가리켜야하기때문이죠.
#include <iostream> //2316
#include <queue>
#include <vector>
#define MAX (802)
constexpr int OUT = 401;
constexpr int INF = 987654321;
std::vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int networkFlow(int start, int end){
int ans = 0;
while(true){
std::vector<int> visit(MAX, -1);
std::queue<int>q;
q.push(start);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<adj[x].size();++i){
int y = adj[x][i];
if(visit[y] == -1 && c[x][y] - f[x][y] > 0){
visit[y] = x;
q.push(y);
if(y == end) break;
}
}
}
if(visit[end] == -1) break;
int flow = INF;
for(int i = end;i!=start;i=visit[i]) flow = std::min(flow, c[visit[i]][i] - f[visit[i]][i]);
for(int i = end;i!=start;i=visit[i]){
f[visit[i]][i] += flow;
f[i][visit[i]] -= flow;
}
ans += flow;
}
return ans;
}
int main(){
std::cin.tie(0);
std::cout.tie(0);
std::ios_base::sync_with_stdio(0);
int N, P;
std::cin >> N >> P;
for(int i=1;i<=N;++i){
adj[i].push_back(OUT + i);
adj[OUT + i].push_back(i);
c[i][OUT + i] = 1;
}
for(int i=0;i<P;++i){
int a, b;
std::cin >> a >> b;
adj[OUT + a].push_back(b);
adj[b].push_back(OUT + a);
c[OUT + a][b] = 1;
adj[OUT + b].push_back(a);
adj[a].push_back(OUT + b);
c[OUT + b][a] = 1;
}
std::cout << networkFlow(OUT + 1, 2);
}
푸는시간은 40~50분정도 걸린것같습니다.
이번 문제를 풀면서 저도 성장한것같네요..ㅎ
이 문제를 풀면서 분할정복이라는것도 배우게되었습니다.
알고리즘문제는 계속해서 꾸준히 풀면서 실력도 좋아졌으면 좋겠네요..!
궁금한 부분있으시면 댓글로 질문주세요~