글 읽기 - 2316 질문입니다..

smy4024169 2년 전 0

우선 답은 정점분할 사용해서 맞추긴 했습니다

그런데 그 전에 생각했던 풀이가 아래와 같은데, 핵심은 26-29행과 같이 이미 사용되는 edge가 포함된 node는 parent를 보존해 접근하지 못하게 하는 것입니다.

이것도 예제도 잘 돌아가는데, 91%에서 틀리더라고요..

무엇이 문제인지 몰라 질문 드립니다..

#include <bits/stdc++.h>
#define mod 1000000007
#define FIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define priority_queue_(x) priority_queue<x, vector<x>, greater<x>>
#define priority_queue_pair priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
typedef long long ll;
using namespace std;
int ny[4] = { 1, 0, -1, 0 };
int nx[4] = { 0, 1, 0, -1 };

int c[1001][1001];
int f[1001][1001];
int parent[1001];

queue<int> kk;

int NETWORK(int start, int end, int N) {
    //총 유량
    int sum = 0;

    //start -> end 경로 한 번에 반복 한 번씩
    while (1) {
        //중복 처리(memset 대신)
        //f가 있다면 이미 사용한 edge니까 놔두고, f가 없을 때만 초기화
        for (int i = 1; i <= N; i++) {
            if (not f[parent[i]][i]) parent[i] = -1;
            if (i == start) parent[i] = -1;
            if (i == end) parent[i] = -1;
        }
        while (kk.size()) kk.pop();
        kk.push(start);
        parent[start] = start;

        //BFS로 잔여 그래프 만들기
        while (kk.size() and (parent[end] == -1)) {
            int from = kk.front(); kk.pop();

            for (int to = 1; to <= N; to++) {
                if (c[from][to] - f[from][to] <= 0) continue;
                if (not (parent[to] == -1)) continue;
                parent[to] = from;
                kk.push(to);
            }
        }
        //더 이상 잔여 그래프 생성 안되면 break
        if (parent[end] == -1) break;

        //추가할 유량은 지나온 경로의 최솟값
        int minnum = INT_MAX, p = end;
        while (not (p == start)) {
            minnum = min(c[parent[p]][p] - f[parent[p]][p], minnum);
            p = parent[p];
        }

        //유량 추가
        p = end;
        while (not (p == start)) {
            f[parent[p]][p] += minnum;
            f[p][parent[p]] -= minnum;
            p = parent[p];
        }
        sum += minnum;
    }
    return sum;
}

int main() {
    FIO;
    int N, M; cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int from, to; cin >> from >> to;
        //양방향
        c[from][to] = 1;
        c[to][from] = 1;
    }
    cout << NETWORK(1, 2, N);
}