[2316번] 도시 왕복하기

문제 출처 :

https://www.acmicpc.net/problem/2316

알고리즘 분석 :

문제 해결에 필요한 사항

1. 네트워크 플로우 :: http://www.crocus.co.kr/741

2. 최대 유량

문제에서 요구하는 내용은 도시를 한번만 방문해야된다는 것이다.

따라서 한번 방문한 도시를 방문해서는 안되고, 그 도시에 대해 처리를 해주어야한다.

그 방법으로 다른 사람들의 풀이를 보니 노드를 2개로 쪼개어 연결하는 방식도 있지만, 필자는 조금 다른 방식으로 생각해보았다.

visit배열을 이용하여 도시의 방문 여부를 계속해서 update해주는 방식을 생각하였다.

사실 이 문제를 최대 유량으로 풀 때 각 간선의 용량이 1이라 visit배열을 update해줄 필요는 없지만,

다른 문제에서 용량이 1보다 클 경우 이 방식을 이용하면 해결 할 수 있는 문제가 있을 것이기 때문에 visit를 update해주는 과정까지 적어두었다.

memcpy를 통해 update 해주는 과정이 아래 들어있고,

그 외에는 네트워크 플로우의 에드몬드 카프 방식으로 해결이 가능하다.

(이 문제에서 tmp배열을 지우고, memcpy 배열을 지워도 유량이 1이기에 AC를 받는다.)

(2017. 11. 10 수정)

위의 방법대로 생각하고 처음에 글을 작성하였는데 네트워크 플로우에 대한 개념이 부족했던 것이 절실히 드러나는 순간이다.

위의 방식대로 노드 자체를 막아버린다면 유량을 나타내는 f배열을 이용할 수 없게 되어 우리는 정확한 flow를 알 수 없게 된다.

따라서 문제에서는 노드를 한번만 써야한다 할지라도 노드를 visit를 이용하여 막으면 안되고, 노드 하나를 in,out 노드로 분리하여 노드 속의 유량을 1로 설정하여 각 노드는 단 한번만 쓸 수 있도록 변경해준다.

소스 코드 : 

AC 코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
 
#define MAX 900
#define INF 987654321
 
using namespace std;
 
int c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량
int f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량
bool adj[MAX][MAX];
 
int main()
{
    int n, p;
 
    for (int i = 3; i <= 400; i++)
    {
        c[i][i + 400] = 1;
 
        adj[i][i + 400] = 1;
        adj[400 + i][i] = 1;
    }
 
    // 입력
    scanf("%d %d", &n, &p);
    for (int i = 0; i < p; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        c[from + 400][to] = 1;
        c[to + 400][from] = 1;
 
        adj[from + 400][to] = 1;
        adj[to][from + 400] = 1;
        adj[to + 400][from] = 1;
        adj[from][to + 400] = 1; // 역방향 간선 추가
    }
 
 
    int totalFlow = 0, S = 401, T = 2; // S :: source, T :: sink
    
    while (1)
    {
        int prev[MAX];
        memset(prev, -1, sizeof(prev));
 
        queue<int> q;
        q.push(S);
 
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            //cout << "!!!!!!!! cur !!!!!!!!!! " << cur  << endl;
            for (int i = 1; i < MAX; i++)
            {
                if (adj[cur][i] == 0)
                    continue;
 
                int next = i;
 
                //cout << "next :: " << next << endl;
                if (prev[next] != -1)
                    continue;
 
                //cout << "c[" << cur << "][" << next << "]" << c[cur][next] << " " << "f[" << cur <<"][" << next << "]" << f[cur][next] << endl;
                if (c[cur][next] - f[cur][next] > 0)
                {
                    q.push(next);
 
                    prev[next] = cur;
 
                    if (next == T)
                        break;
                }
            }
        }
 
 
        if (prev[T] == -1)
            break;
 
        int flow = INF;
 
        for (int i = T; i != S; i = prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
 
        for (int i = T; i != S; i = prev[i])
        {
            //cout << " i : " << i << endl;
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
 
        totalFlow += flow;
    }
 
    printf("%d\n", totalFlow);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

플로우 이해가 부족했던 WA 코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
 
#define MAX 401
#define INF 987654321
 
using namespace std;
 
int c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량
int f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량
bool visit[MAX];
bool tmp[MAX];
 
int main()
{
    int n, p;
 
    memset(c, 0, sizeof(c));
    memset(f, 0, sizeof(f));
 
    vector<int> adj[MAX];
    
    // 입력
    scanf("%d %d", &n, &p);
    for(int i = 0; i < p; i ++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        c[from][to] = 1; // 용량을 추가해준다.
        c[to][from] = 1;
 
        adj[from].push_back(to);
        adj[to].push_back(from); // 역방향 간선 추가
    }
 
    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;
 
            //cout << "cyr :: " << cur << endl;
            for (int i = 0; i < adj[cur].size(); i++)
            {
                int next = adj[cur][i];
 
                // next를 방문하였다면 continue
                if (prev[next] != -1)
                    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;
 
        int flow = INF;
 
        // 지금까지 구한 경로 상에서 가장 flow가 낮은 곳을 구한다.
        for (int i = T; i != S; i = prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
        
        // 해당 경로에 flow를 보낸다.
        // 그리고 역방향으로는 flow를 빼준다.
        memcpy(visit, tmp, sizeof(tmp));
 
        for (int i = T; i != S; i = prev[i])
        {
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
 
            if (i != S && i != T)
                visit[i] = true;
        }
 
        memcpy(tmp, visit, sizeof(visit));
 
        totalFlow += flow;
    }
 
    printf("%d\n", totalFlow);        
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>