글 읽기 - 최대 유량 문제 질문드립니다

dotoleeoak 4년 전 0

문제는 디닉으로 풀었고 아래처럼 제출했는데 TLE가 뜨네요...

제가 제출한 맞은 코드랑 비교해보니까 라인 90 ~ 94에서 무한루프 도는거 같은데

왜 무한루프가 도는 건가요??

#include <bits/stdc++.h>
using namespace std;

int T, n, m, ans, src, sink;
int board[51][51];
int level[2550];
int flow[2550][2550];
vector<vector<int>> adj;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

bool inRange(int y, int x) {
    return 0 <= y && y < n && 0 <= x && x < m;
}

bool bfs() {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(src);
    level[src] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto nxt : adj[cur]) {
            if (level[nxt] == -1 && flow[cur][nxt] > 0) {
                level[nxt] = level[cur] + 1;
                q.push(nxt);
            }
        }
    }
    return level[sink] != -1;
}

int dfs(int cur, int cap) {
    if (cur == sink) return cap;
    for (auto nxt : adj[cur]) {
        if (level[cur] + 1 == level[nxt] && flow[cur][nxt] > 0) {
            int val = dfs(nxt, min(cap, flow[cur][nxt]));
            if (val > 0) {
                flow[cur][nxt] -= val;
                flow[nxt][cur] += val;
                return val;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        ans = 0;
        src = n * m;
        sink = src + 1;
        memset(flow, 0, sizeof(flow));
        adj = vector<vector<int>>(n * m + 2);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                cin >> board[i][j];
                ans += board[i][j];
            }

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int cur = i * m + j;
                if ((i + j) & 1) {
                    adj[cur].push_back(sink);
                    adj[sink].push_back(cur);
                    flow[cur][sink] = board[i][j];
                } else {
                    adj[cur].push_back(src);
                    adj[src].push_back(cur);
                    flow[src][cur] = board[i][j];
                    for (int d = 0; d < 4; d++) {
                        int ny = i + dy[d];
                        int nx = j + dx[d];
                        if (!inRange(ny, nx)) continue;
                        int ncur = ny * m + nx;
                        adj[cur].push_back(ncur);
                        adj[ncur].push_back(cur);
                        flow[cur][ncur] = INT_MAX;
                    }
                }
            }

        while (bfs()) {
            while (true) {
                int val = dfs(src, INT_MAX);
                if (!val) break;
                ans -= val;
            }
        }

        cout << ans << '\n';
    }
}

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

문제

문제

출처

ICPC

최대 유량 문제 질문드립니다

dotoleeoak 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말