글 읽기 - Maximum Flow 공부해서 짜봤는데 틀렸습니다

iriszero 8년 전 0

0번을 source, N+M+1번을 sink

사람은 1~N, 작업은 N+1~ N+M까지

capacity는

a. src와 사람은 2

b. 사람과 작업은 1

c. 작업과 sink는 1

로 해서 maximum flow 를 구했는데 accepted를 못 받았습니다.

어디가 잘못된 건지 알 수 있을까요?

https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp... 의 pseudo code 참고했습니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
const int INF = 987654321;
using namespace std;

int min(int a, int b) {
    return a<b? a:b;
}
pair<int, vector<int>> BFS(const vector<vector<int>> &cap, const vector<vector<int>> &graph,
                           vector<vector<int>> &flow, const int src, const int sink) {
    vector<int> prv(graph.size(), -1);
    vector<int> M(graph.size(), -1);
    prv[src]=-2; M[src] = INF;
    
    queue<int> q; q.push(src);
    
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            if (cap[u][v] - flow[u][v] > 0 && prv[v] == -1) {
                prv[v] = u;
                M[v] = min(M[u], cap[u][v] - flow[u][v]);
                if (v!=sink) {
                    q.push(v);
                }
                else {
                    return make_pair(M[sink], prv);
                }
            }
        }
    }
    return make_pair(0, prv);
}

//Edmonds Karp Algorithm
int MaxFlow(const vector<vector<int>> cap, const vector<vector<int>> graph,
            const int src, const int sink) {
    int sum =0;
    vector<vector<int>> flow(graph.size(), vector<int>(graph.size(),0));
    
    while(true) {
        //BFS
        pair<int, vector<int>> ret = BFS(cap, graph, flow, src, sink);
        int m = ret.first; vector<int> &prv = ret.second;

        if (m == 0) break;
        sum+= m;
        
        int v= sink;
        while(v != src) {
            int u = prv[v];
            flow[u][v] += m;
            flow[v][u] -= m;
            v = u;
        }
    }
    return sum;
}

int main(void) {
    int N, M; scanf("%d %d", &N, &M);
    vector<vector<int>> graph(N+M+2), cap(N+M+2, vector<int>(N+M+2, 0));
    for (int i=1; i<=N; i++) {
        int K; scanf("%d", &K);
        graph[0].push_back(i);
        cap[0][i] = 2;
        for (int j=1; j<=K; j++) {
            int work; scanf("%d", &work);
            graph[i].push_back(N+work);
            cap[i][N+work] = 1;
        }
    }
    for (int i=N+1; i<=N+M; i++) {
        graph[i].push_back(N+M+1);
        cap[i][N+M+1] = 1;
    }
    
    printf("%d\n", MaxFlow(cap,graph, 0, N+M+1));
}

iriszero 8년 전 0

@cubelover 죄송한데 이유를 좀 알 수 있을까요???

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

문제

문제

출처

ICPC

Maximum Flow 공부해서 짜봤는데 틀렸습니다

iriszero 8년 전 0

iriszero 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말