글 읽기 - 시간 초과 해결하고 싶습니다ㅠㅠ

qkrwns1714 4년 전 0

계속 시간초과가 나네요... 어떻게 해결할 수 있을까요?
/*
1. 안되는 경우이면 -1 출력(지민이의 팀이 해야하는 경기의 수 != 한수의 팀이 해야하는 경기의 수)** 종료 --- O(1)

2. 유량 그래프 생성(sourse와 지민이의 팀을 잇고(가중치는 각 팀원이 해야 하는 경기의 수), sink와 한수의 팀을 잇고(이하동문), 지민이의 팀과 한수의 팀을 잇는다(가중치는 1)) ---- O(N*M)

3. 네트워크 플로우 계산 ---- O((N*M)^2*(N+M))

4. 안되는 경우이면 -1 출력(최대 유량 != 총 해야하는 경기의 수((지민이의 팀이 해야하는 경기의 수 + 한수의 팀이 해야하는 경기의 수)/2))** 종료 ---- O(1)

{
    5. 현재 유량이 1인 간선이고 방문하지 않았던 간선 중 가장 번호가 작은 지민이의 팀과 이어져 있고 그 중 가장 번호가 작은 한수의 팀원과 이어져 있는 간선 탐색 O(N*M)
            5:예외. 만약 모든 간선을 방문했다면 해당 대진표를 출력** 종료 O(N*M)

    6. 탐색된 간선의 한계 유량을 0으로 만들고, 그 이상의 번호인 간선들을 모두 초기화(초기화 = 현제 유량을 0으로 만들고(역방향의 유량도) 양 정점과 sourse 또는 sink와 이어져 있는 간선의 현재 유량-1) O(N*M)

    7. 다시 한번 네트워크 플로우 실행 ----O((N*M)^2*(N+M))
        7-1. 안되는 경우이면 6번 전의 대진표로 되돌린 후, 해당 간선을 방문했던 간선으로 처리------------------>5번으로 ---- O(N*M)
            7-1:되돌리는 법. 딴 배열에 저장했던 pipe와 npip의 정보를 옮김.

        7-2. 된다면----------------------> 5번으로 ---- O(1)
}O((N*M)^3*(N+M))

--최대 1562500000000 1조 5625만번
*/

#include <bits/stdc++.h>
#include <queue>

using namespace std;

const int MAX = 103;

vector<int> graph[MAX]; // 간선 저장
bool visited[MAX][MAX]; // 방문 여부 저장
int pipe[MAX][MAX], npip[MAX][MAX]; // pipe[i][j] i에서 j로 가는 간선의 최대 유량, npip[i][j] i에서 j로 가는 간선의 현재 유량
int expipe[MAX][MAX], exnpip[MAX][MAX]; // pipe와 npip의 값을 임시로 저장할 배열
int N, M; // 지민이의 팀의 팀원 수,  한수의 팀의 팀원 수
int n, m; // 지민이의 팀이 해야 하는 총 경기의 수, 한수의 팀이 해야 하는 총 경기의 수
int a[52], b[52]; // a[i] = 지민이의 팀의 i 번째 팀원이 해야 하는 경기의 수, b[i] = 한수의 팀의 i번째 팀원이 해야 하는 경기의 수,
int value; // 네트워크 플로우의 결과값
int exvalue; // value를 저장할 임시함수
int s, e; // s = sourse, e = sink
queue<int> que;
int bumo[MAX];


void flow(){
    while(1){
        while(!que.empty()){
            que.pop();
        }
        que.push(s);
        fill(bumo, bumo+MAX, -1);
        //cout << "7-1*" << " ";
        while(bumo[e] == -1 && !que.empty()){
            int now = que.front();
            que.pop();
            for(int i : graph[now]){
                if(bumo[i] == -1 && pipe[now][i] - npip[now][i] > 0){
                    bumo[i] = now;
                    if(i == e){
                        break;
                    }
                    que.push(i);
                }
            }
        }
//        cout << "7-2*" << " ";
        if(bumo[e] == -1){
            break;
        }
        int maxx = 987654321;
        for(int i = e ; i != s ; i = bumo[i]){
            maxx = min(maxx, pipe[bumo[i]][i] - npip[bumo[i]][i]);
        }
      //  cout << value << " ";
        value += maxx;
        for(int i = e ; i != s ; i = bumo[i]){
            npip[bumo[i]][i] += maxx;
            npip[i][bumo[i]] -= maxx;
        }
      //  cout << "7-3*" << " ";
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // 전처리 시작 (입력 및 n, m 계산)
    cin >> N >> M;
    for(int i = 1 ; i <= N ; i++){
        cin >> a[i];
        n += a[i];
    }
    for(int j = 1 ; j <= M ; j++){
        cin >> b[j];
        m += b[j];
    }
    // 전처리 끝
    // 1번 시작
    //cout << 1 << " ";
    if(n != m){
        cout << -1;
        return 0;
    }
    // 1번 끝
    // 전처리 시작 (sourse와 sink 정하기)
    s = 0, e = N+M+1;
    // 2번 시작
   // cout << 2 << " ";
    for(int i = 1 ; i <= N ; i++){
        graph[s].push_back(i);
        graph[i].push_back(s);
        pipe[s][i] = a[i];
    }
    for(int i = N+1 ; i <= N+M ; i++){
        graph[i].push_back(e);
        graph[e].push_back(i);
        pipe[i][e] = b[i-N];
    }
    for(int i = 1 ; i <= N ; i++){
        for(int j = N+1 ; j <= N+M ; j++){
            graph[i].push_back(j);
            graph[j].push_back(i);
            pipe[i][j] = 1;
        }
    }
    // 2번 끝
    // 3번 시작
   // cout << 3 << " ";
    flow();
    // 3번 끝
    // 4번 시작
   // cout << 4 << " ";
    if(value != n){
        cout << -1;
        return 0;
    }
    // 4번 끝
    // 전처리 시작(5번의 간선을 저장할 수 2개, 사전순으로 더 낮은 대진표 제거)
    int f = 0, d = 0; // f = 간선의 시작점, d = 간선의 끝점
    for(int i = 1 ; i <= N; i++){
        for(int j = N+1 ; j <= N+M ; j++){
            if(npip[i][j] == 1){
                d=1;
                break;
            }
            else{
                pipe[i][j] = 0;
            }
        }
        if(d == 1){
            break;
        }
    }
    //전처리 끝
    while(1){
       /* for(int i = 1 ; i <= N ; i++){
            for(int j = N+1 ; j <= N+M ; j++){
                if(npip[i][j] == 1){
                    cout << 1;
                }
                else{
                    cout << 0;
                }
            }
            cout << "\n";
        }
        cout << "\n";
        cout << "-----" << "\n";
        for(int i = 1 ; i <= N ; i++){
            for(int j = N+1 ; j <= N+M ; j++){
                if(visited[i][j] == true){
                    cout << 1;
                }
                else{
                    cout << 0;
                }
            }
            cout << "\n";
        }
        cout << "\n";*/
        f = 0;
        // 5번 시작
        //cout << 5 << " ";
        for(int i = 1 ; i <= N ; i++){
            for(int j = N+1 ; j <= N+M ; j++){
                if(npip[i][j] == 1 && visited[i][j] == false){
                    f = i;
                    d = j;
                    break;
                }
                if(f == 0 && npip[i][j] == 0){
                    visited[i][j] = true;
                    pipe[i][j] = 0;
                }
            }
            if(f){
                break;
            }
        }
        // 5번 끝
        // 5번 예외 시작
        if(f == 0){
            //cout << "5:예외" << "\n";
            for(int i = 1 ; i <= N ; i++){
                for(int j = N+1 ; j <= N+M ; j++){
                    if(npip[i][j] == 1){
                        cout << 1;
                    }
                    else{
                        cout << 0;
                    }
                }
                cout << "\n";
            }
            break;
        }
        // 5번 예외 끝
        // 전처리 시작(expipe와 exnpip에 정보 복사)
        for(int i = 1 ; i <= N ; i++){
            for(int j = N+1 ; j <= N+M ; j++){
                expipe[i][j] = pipe[i][j];
                exnpip[i][j] = npip[i][j];
                exnpip[j][i] = npip[j][i];
            }
        }
        exvalue = value;
        for(int i = 1 ; i <= N ; i++){
            expipe[0][i] = pipe[0][i];
            exnpip[i][0] = npip[i][0];
            exnpip[0][i] = npip[0][i];
        }
        for(int i = N+1 ; i <= N+M ; i++){
            expipe[i][e] = pipe[i][e];
            exnpip[i][e] = npip[i][e];
            exnpip[e][i] = npip[e][i];
        }
        // 전처리 끝
        // 6번 시작
        //cout << 6 << " ";
        pipe[f][d] = 0;
        for(int i = f ; i <= N ; i++){
            if(i != f){
                for(int j = N+1 ; j <= N+M ; j++){
                    if(npip[i][j] == 1){
                        npip[i][j] = 0;
                        npip[j][i] = 0;
                        npip[s][i]--;
                        npip[i][s]++;
                        npip[j][e]--;
                        npip[e][j]++;
                        value--;
                    }
                }
            }
            else{
                for(int j = d ; j <= N+M ; j++){
                    if(npip[i][j] == 1){
                        npip[i][j] = 0;
                        npip[j][i] = 0;
                        npip[s][i]--;
                        npip[i][s]++;
                        npip[j][e]--;
                        npip[e][j]++;
                        value--;
                    }
                }
            }
        }
        // 6번 끝
        // 7번 시작
        //cout << 7 << " ";
        flow();
        //7번 끝;
        //7-1번 시작
        if(value != n){
            //cout << 7-1 << " ";
            for(int i = 1 ; i <= N ; i++){
                for(int j = N+1 ; j <= N+M ; j++){
                    pipe[i][j] = expipe[i][j];
                    npip[i][j] = exnpip[i][j];
                    npip[j][i] = exnpip[j][i];
                }
            }
            value = exvalue;
            for(int i = 1 ; i <= N ; i++){
                pipe[0][i] = expipe[0][i];
                npip[0][i] = exnpip[0][i];
                npip[i][0] = exnpip[i][0];
            }
            for(int j = N+1 ; j <= N+M ;j++){
                pipe[j][e] = expipe[j][e];
                npip[j][e] = exnpip[j][e];
                npip[e][j] = exnpip[e][j];
            }
            visited[f][d]= true;
        }
        //7-1번 끝
        //7-2번 실행
        //7-2번 끝
    }
    return 0;
}
/*
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
10 10
2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2
10 10
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3
10 10
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
20 20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
30 30
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29
30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
40 40
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/
qkrwns1714 4년 전 0

graph를 pair<int, bool>로 선언한 걸
int형으로 바꾸고,
bool visited[MAX][MAX];
를 만들어주니 메모리 초과는 해결됬네요. 근데 시간초과가 또 나는군요....
qkrwns1714 4년 전 0

10 10
9 9 9 9 9 9 9 9 9 9
의 값이 이상하게 나와서 보니 visited의 값을 잘못 설정했엇네요.
qkrwns1714 4년 전 0

한번 네트워크 플로우를 다닉 알고리즘으로 짜봐야 겠어요....
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

시간 초과 해결하고 싶습니다ㅠㅠ

qkrwns1714 4년 전 0

qkrwns1714 4년 전 0

qkrwns1714 4년 전 0

qkrwns1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
