[C++] 3640번 제독 - 최대 유량, 최소 비용 최대 유량

1. 문제

• 한 중간 지점에서 두 전함이 겹치지 않는 뱃길과 중간지점을 택해 목적지에 도달한다. 중간 지점과 중간 지점 사이에는 사용해야 하는 포탄의 수가 정해져 있을 때 사용해야 하는 포탄의 최소 수를 구하시오.

2. 재정의

• 서로 겹치지 않는 두 경로의 가중치 합의 최솟값을 구하시오.

3. 해결방법

• 용량을 2로 설정하면 두 개의 경로가 만들어 지며 bfs로 최단 경로를 탐색하면 된다.

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

#define pii pair<int, int>
#define fi first

using namespace std;

const int INF = 987654321;
const int MAX_V = 2003;
const int OUT = 1000;

//간선 구조체
struct Edge {
    //next로 가는 용량이 capacity이고 유량이 flow만큼 흐르며 가중치가 cost인 간선
    int next, capacity, flow=0, cost;
    Edge* rev;
    Edge(){};
    Edge(int _next, int _capacity, int _cost) : next(_next), capacity(_capacity), cost(_cost) {};
    
    //흐를 수 있는 유량
    int Remain() {
        return capacity - flow;
    }
    //유량 흘려주기
    void Push(int x) {
        flow += x;
        rev->flow -= x;
    }
};
//방향 그래프
vector<Edge*> adj[MAX_V];

//그래프 간선 생성하기
void makeEdge(int u, int v, int capa, int c) {
    Edge *uv = new Edge(v, capa, c), *vu = new Edge(u, 0, -c);
    uv->rev = vu, vu->rev = uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

int S, E;
//중간 지점의 수 v, 뱃길의 수 e
int v, e;

void input() {
    cin >> v >> e;
    if(cin.eof()) exit(0);
    
    for(int i=0; i<MAX_V; i++)
        adj[i].clear();
    
    S = 1; E = v;
    
    //2개의 경로가 존재
    makeEdge(1, 1+OUT, 2, 0);
    makeEdge(E, E+OUT, 2, 0);
    //정점 분리
    for(int i=2; i<E; i++)
        makeEdge(i, i+OUT, 1, 0);
    //뱃길에 맞은 간선 만들어주기
    for(int i=0; i<e; i++) {
        int a, b, c;
        
        cin >> a >> b >> c;
        makeEdge(a+OUT, b, 1, c);
    }
}

int MCMF() {
    //최소 비용
    int minCost = 0;
    
    while(1) {
        //최대 유량 알고리즘 용 부모와 최단 거리
        int parent[MAX_V], dist[MAX_V];
        Edge *path[MAX_V];
        queue<int> q;
        
        //배열 초기화
        memset(parent, -1, sizeof parent);
        fill(dist, dist+MAX_V, INF);
        
        //dfs
        dist[S] = 0;
        q.push(S);
        
        while(!q.empty()) {
            int here = q.front(); q.pop();
            
            for(auto e : adj[here]) {
                //탐색할 곳
                int there = e->next;
                //더 최단 경로가 존재할 경우 갱신
                if(e->Remain() > 0 && dist[there] > dist[here] + e->cost) {
                    dist[there] = dist[here] + e->cost;
                    parent[there] = here;
                    path[there] = e;
                    q.push(there);
                }
            }
        }
        //더 이상의 증가 경로가 없으므로 종료
        if(parent[E] == -1)
            break;
        
        //탐색한 경로로 흘려줄 수 있는 최대 유량
        int flow = INF;
        for(int p = E; p!=S; p = parent[p])
            flow = min(flow, path[p]->Remain());
        for(int p = E; p!=S; p = parent[p]) {
            minCost += flow * path[p]->cost;
            path[p]->Push(flow);
        }
    }
    
    return minCost;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    while(1) {
        input();
        
        cout << MCMF() << '\n';
    }
    
    return 0;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.