[Baekjoon,2316]도시 왕복하기 2

해결

다들 visited와 같은 배열을 만들이 이미 경로가 형성된 정점을 처리하여 해결하려고 했을 것이다. 하지만 이러한 방법으로는 flow의 역방향을 통해 증가 경로를 찾지 못하기 때문에 다른 방법을 찾아야 한다.

각 정점을 쪼개자

각 정점을 in 정점과 out 정점 둘로 나누고 그 사이의 간선의 용량을 1로 설정하면 유량이 흐른 경우 다시 흐를 수 없기 때문에 이 문제를 해결할 수 있다.
그리고 flow가 역방향을 탐색할 수도 있다.

구현시 모든 정점을 둘로 쪼개는 대신 1번 도시와 2번 도시는 쪼개진 사이의 간선 용량을 무한대로 두어 계속 방문할 수 있게 하였다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

enum { SRC, SNK };

const int INF=987654321;
const int MAX_V=810;

int V,E;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];

int networkFlow(int source, int sink)
{
    int totalFlow=0;
    memset(flow,0,sizeof(flow));
    while(true)
    {
        // 증가 경로를 찾는다. 
        queue<int> q;
        vector<int> parent(V,-1);
        q.push(source);
        parent[source]=source;
        while(!q.empty() && parent[sink]==-1)
        {
            int here=q.front(); q.pop();
            for(int there=0;there<V;++there)
                if(parent[there]==-1 && capacity[here][there]-flow[here][there]>0)
                {
                    parent[there]=here;
                    q.push(there);
                }
        }
        // 더 이상 증가 경로가 없는 경우
        if(parent[sink]==-1)
            break;
        // 증가 경로에 유량을 흘려 보낸다.
        for(int p=sink;p!=source;p=parent[p])
        {
            flow[parent[p]][p]+=1;
            flow[p][parent[p]]-=1;
        }
        totalFlow+=1;
    }
    return totalFlow;
}

int main()
{
    cin>>V>>E;
    V*=2;
    memset(capacity,0,sizeof(capacity));
    // 각 정점을 2개로 분리하고 나뉜 정점 사이 간선(in->out)의 용량을 1로 설정한다.
    for(int i=0;i<V;i+=2)
        capacity[i][i+1]=1;
    // 1번과 2번 정점은 계속 방문 할 수 있다.
    capacity[0][1]=capacity[2][3]=INF;
    
    for(int i=0;i<E;++i)
    {
        int a,b;
        cin>>a>>b;
        --a;--b;
        // 양방향 간선이다.  
        // out -> in 으로 향해야 한다.
        capacity[2*a+1][2*b]=1;
        capacity[2*b+1][2*a]=1;
    }
    
    cout<<networkFlow(SRC*2,SNK*2+1)<<endl;
    return 0;
}