글 읽기 - 반례가 궁금합니다

jungin0507 3년 전 0

일단 대진표를 먼저 구해놓은 다음에,

i, j를 돌면서 flow[i][j]를 0으로 만들 수 있는 새로운 경로가 있다면 그 경로로 flow를 흘려보내서 flow[i][j]를 0으로 만들게 만들었습니다.

대신 이때 찾는 경로는 이미 앞에서 바꿔놓았던 경로들에 영향을 미치지 않는 경로입니다. from이라는 변수를 사용해서 이를 처리했습니다.

오랫동안 생각했는데 아무리 생각해도 틀린 부분을 모르겠습니다.

/해결/

#include <bits/stdc++.h>

#define pii pair<int, int>
#define pdi pair<double, int>
#define pid pair<int, double>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define INF 1e9 + 5
#define vi vector<int>
#define sq(x) ((x) * (x))
#define FOR(i, n) for(int i=0; i < (n) ; ++i)

typedef long long ll;

using namespace std;

int A[100], B[100];
int N, M;
int flow[100][100];
bool visited[100];
int from = -1;

bool dfs(int here) {
    if (from != -1 && here <= from) return false;
    if (visited[here]) return false;
    visited[here] = true;

    for (int there = 0; there < M; ++there) {
        if (flow[here][there]) continue;
        if (B[there]) {
            flow[here][there] = 1;
            --B[there];
            return true;
        }
        else {
            for (int a = 0; a < N; ++a) {
                if (flow[a][there] == 0) continue;
                if (dfs(a)) {
                    flow[a][there] = 0;
                    flow[here][there] = 1;
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;

    int chk = 0;
    int sum1 = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        sum1 += A[i];
    }
    int sum2 = 0;
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
        sum2 += B[i];
    }

    int cnt = 0;
    for (int a = 0; a < N; ++a) {
        while (A[a]) {
            memset(visited, false, sizeof(visited));
            if (dfs(a)) {
                ++cnt;
                --A[a];
            }
            else {
                break;
            }
        }
    }

    if (cnt != sum1 || cnt != sum2 || sum1 != sum2) {
        cout << -1 << "\n";
        return 0;
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (flow[i][j] == 0) continue;
            for (int k = j + 1; k < M; ++k) {
                if (flow[i][k] == 1) continue;
                if (flow[i][j] == 0) break;
                for (int l = i + 1; l < N; ++l) {
                    if (flow[l][k] == 0) continue;
                    memset(visited, false, sizeof(visited));
                    flow[i][j] = 0;
                    B[j] += 1;
                    from = i;
                    if (dfs(l)) {
                        flow[i][k] = 1;
                        flow[l][k] = 0;
                        break;
                    }
                    else {
                        flow[i][j] = 1;
                        B[j] -= 1;
                    }
                }
            }
            
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j)
            cout << flow[i][j];
        cout << "\n";
    }

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 궁금합니다

jungin0507 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말