글 읽기 - 에드몬드 카프 틀리는 이유

(追記) (追記ここまで)

에드몬드 카프 틀리는 이유

11378번 - 열혈강호 4

mwy3055 5년 전 0

스포일러 주의: 이 질문글에는 정답과 매우 유사한 코드가 있습니다.

일단 이분 매칭으로 풀긴 했습니다만, 네트워크 플로우로도 구현해 보려 했습니다.

그래프는 source(0), 직원(1 ~ n), 일(n+1 ~ n+m), sink(n+m+1)로 구성했습니다. source로부터 각 직원에 용량이 k+1인 간선을 연결하고, 직원과 일, 일과 sink를 모두 용량 1인 간선으로 연결하여 에드몬드 카프 알고리즘으로 네트워크 플로우를 구현했습니다.

그런데 계속해서 오답을 받습니다. 구글에 검색해 보면 디닉으로 풀어야 한다는 말도 있는데, 에드몬드 카프를 사용하면 틀리는 건가요? 아니면 구현에 문제가 있나요?

#include <bits/stdc++.h>
std::vector<int> graph[2002];
int cap[2002][1002], flow[2002][2002];
int solve(int start, int end)
{
 std::vector<int> track(end - start + 1);
 int rtn = 0;
 while (true)
 {
 std::fill(track.begin(), track.end(), -1);
 std::queue<int> q;
 q.push(start);
 while (!q.empty())
 {
 auto top = q.front();
 q.pop();
 for (auto &adj : graph[top])
 {
 if (cap[top][adj] - flow[top][adj] > 0 && track[adj] == -1)
 {
 q.push(adj);
 track[adj] = top;
 if (adj == end)
 break;
 }
 }
 }
 if (track[end] == -1)
 break;
 int maxflow = 0x3f3f3f3f, cur = end;
 while (cur != start)
 {
 auto &bef = track[cur];
 maxflow = std::min(maxflow, cap[bef][cur] - flow[bef][cur]);
 cur = bef;
 }
 cur = end;
 while (cur != start)
 {
 auto &bef = track[cur];
 flow[bef][cur] += maxflow;
 flow[cur][bef] -= maxflow;
 cur = bef;
 }
 rtn += maxflow;
 }
 return rtn;
}
void connect(int a, int b, int capacity)
{
 graph[a].push_back(b);
 graph[b].push_back(a);
 cap[a][b] = capacity;
}
int main()
{
 std::ios::sync_with_stdio(false);
 std::cin.tie(0);
 int n, m, k;
 std::cin >> n >> m >> k;
 for (int i = 1; i <= n; i++)
 {
 connect(0, i, k + 1);
 int p;
 std::cin >> p;
 for (int j = 0; j < p; j++)
 {
 int w;
 std::cin >> w;
 connect(i, n + w, 1);
 }
 }
 for (int i = 1; i <= m; i++)
 {
 connect(n + i, n + m + 1, 1);
 }
 std::cout << solve(0, n + m + 1) << '\n';
}

lovinix 5년 전 1

에드몬드 카프는 아무 잘못이 없습니다.. 그냥 풀이가 틀렸습니다.

반례 드리겠습니다. 아마 반례보시면 어디가 틀렸는지 바로 아실거라 생각합니다.

INPUT

2 4 1
2 1 2
2 3 4

OUTPUT

ANSWER

mwy3055 5년 전 0

답변 감사합니다. 해당 문제를 수정했으나 또다른 문제가 있는 것 같습니다. 스스로 찾아보겠습니다.

mwy3055 5년 전 0

해결했습니다. 벌점을 부여하기 전에 모든 직원이 최소한 하나의 일을 할 수 있기 때문에, 처음에 source와 직원 사이의 용량을 1로 설정해서 구한 값과 용량을 k 늘려서 구한 값을 더한 값이 정답이 됩니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

에드몬드 카프 틀리는 이유

mwy3055 5년 전 0

lovinix 5년 전 1

mwy3055 5년 전 0

mwy3055 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말