[7616번] 교실로 가는 길

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

2. 최대 유량

[2316번] 도시 왕복하기 :: http://www.crocus.co.kr/742 문제를 꼭 풀고 이 문제를 접했으면 좋겠다.

이 문제는 위의 문제의 상위 버전이므로, 위의 내용을 이해한다면 이 문제도 풀 수 있다.

이 문제를 풀면서 엄청 많은 WA를 받았고, 결국 최종적으로 AC를 받게 되었다.

문제 입력부터 이해가 잘 안되는 부분이 많았다.

그리고 나중에 테스트 케이스를 어떡하다보니 얻게되어 돌려보니, 겹치지 않는 경로가 K개 이상이 있는 경우가 존재했다.

따라서 K개 이상이어도 K개만 출력하도록 해야하는데 그 부분에서 계속 틀리고 있었다.

입력 부분부터 심상치가 않다.

입력 부분은 already와 chk부분이 없어도 된다. 하지만 없으면 adj 벡터에 계속해서 같은 값이 들어갈 수 있다.

예를들어 첫번째 테스트 케이스가 아래와 같이 생겼지만

3 5
3 4 5
3 4 5
1 2
1 2
1 2

3 5
3 3 3 3 3 3 3 3 3 4 4 4 4 4 5
3 4 3 3 3 3 3 4 5 3 3 4 5 5
1 2 1 2 1 2 1 2 1 2 1 1 2 2
1 2 2 1 2 1
1 2 2

이렇게도 들어올 수 있기에 이러한 과정을 방지해주기 위해 already와 chk배열을 두었다.

그 아래는 에드몬드 카프 알고리즘을 통해 최대 유량을 확인하는데 memcpy를 통해 visit의 방문 누적을 계속 갱신해주고 있다.

(이 과정은 위의 도시 왕복하기에 링크를 통해 들어가보면 visit에 대한 설명이 있다.)

그리고 아래에는 

f[prev[i]][i] = 1;

f[i][prev[i]] = 0;인데 이 부분은 어짜피 용량이 최대 1이고, 유량은 1또는 0이기에 

에드몬드 카프 알고리즘에서 최소 flow를 찾는 과정을 없애고 다음과 같이 그냥 표시하였다.

마지막으로 totalFlow >= n을 통해 K개 이상의 이동가능한 flow가 있어도 K개만 표시하도록 나타내었다.

소스 코드 : 

(테스트 케이스가 약해서 그런건지 모르겠지만, MAX를 N범위인 5000이 아닌 1000으로해도 통과한다.(700으로해도 통과한다.))

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <stack>
 
#define MAX 5001
#define INF 987654321
 
using namespace std;
 
// 모든 배열은 용량이 1이기에 bool로 선언 가능
// 그리고, 한번만 방문하기에 c, f배열이 2가 될 수 없음
// 무조건 0 또는 1
bool c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량
bool f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량
bool visit[MAX]; // 방문 배열
bool tmp[MAX]; // 방문 배열 복사
bool already[MAX]; // 메모이제이션을 위한 배열
bool chk[MAX]; // 메모이제이션을 위한 배열
 
int main()
{
    int n, p, tCase = 1;
 
    while (1)
    {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        memset(visit, false, sizeof(visit));
        memset(tmp, false, sizeof(tmp));
        memset(already, false, sizeof(already));
        stack<int> st;
 
        vector<int> adj[MAX];
 
        // 입력
        scanf("%d %d", &n, &p);
        if (n == 0 && p == 0)
            break;
 
        for (int i = 1; i <= p; i++)
        {
            // adj 벡터에 중복 입력을 막기위해 이용
            memset(chk, false, sizeof(chk));
 
            while (1)
            {
                int to;
                char ch;
                scanf("%d%c", &to,&ch);
 
                // i에 의해 to에도 이미 값이 들어간다면 중복이기에
                // 나중에 to가 i가될 때 to에서 i로 값이 들어오는것을 방지
                if(!already[i])
                    already[i] = true;
 
                if (!already[to])
                {
                    // to에 이미 값이 한번 들어왔다면 
                    // 그 값으로 인해 i와 to는 또 중복이 생기는 것을 방지
                    if (!chk[to])
                    {
                        chk[to] = true;
                        c[i][to] = 1;
                        c[to][i] = 1;
 
                        adj[i].push_back(to);
                        adj[to].push_back(i);
                    }
                }
                if (ch == '\n')
                    break;
            }
        }
        
        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;
 
                for (int i = 0; i < adj[cur].size(); i++)
                {
                    int next = adj[cur][i];
 
                    // next를 방문하였다면 continue
                    if (prev[next] != -1 || next == S)
                        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;
            
            // 해당 경로에 flow를 보낸다.
            // 그리고 역방향으로는 flow를 빼준다.
 
            // memcpy를 통해 방문 위치를 계속해서 기록해둔다.(중복 방문 방지)
            memcpy(visit, tmp, sizeof(tmp));
 
            for (int i = T; i != S; i = prev[i])
            {
                st.push(i);
                f[prev[i]][i] = 1;
                f[i][prev[i]] = 0;
 
                if (i != S && i != T)
                    visit[i] = true;
            }
 
            memcpy(tmp, visit, sizeof(visit));
 
            st.push(1);
 
            totalFlow ++;
        }
 
        printf("Case %d:\n", tCase++);
        // n개만 출력(n개 이상의 경로가 있어도)
        if (totalFlow >= n)
        {
            while (!st.empty() && n)
            {
                printf("%d ", st.top());
                if (st.top() == 2)
                {
                    n--;
                    printf("\n");
                }
                st.pop();
            }
        }
 
        else
            printf("Impossible\n");
 
        printf("\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>