글 읽기 - MCMF 소스 질문입니다

david1403 6년 전 0

일반적인 MCMF 로 코드를 짰는데 예외가 발생합니다.

제가 찾은 예외는 7 7 6000처럼 시작날짜와 끝나는 날짜가 같은 경우인데,

to 에서 to+1로 처리를 해주는데도 이런문제가 발생하는 이유가 무엇인가요?

    #include <vector>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #define inf 987654321
    using namespace std;

    int n;
    const int source = 0;
    const int drain = 366;
    vector<vector<int>> v;
    int cap[367][367];
    int flow[367][367];
    int cost[367][367];
    int dist[367];
    int pre[367];
    bool inque[367];

    int main(){
        while(true) {
            scanf("%d", &n);
            v.resize(367);
            if (n == 0)
                return 0;
            memset(cap, 0, sizeof(cap));
            memset(cost, 0, sizeof(cost));
            memset(flow, 0, sizeof(flow));
            for (int i = 0 ; i < n ;i++) {
                int from, to, weight;
                scanf("%d %d %d", &from, &to, &weight);
                
                //to 에서 to+1로 처리해줌
                
                v[from].push_back(to+1);
                v[to+1].push_back(from);
                cost[from][to+1] = -weight;
                cost[to+1][from] = weight;
                cap[from][to+1] = 1;
            }
            
            // 0 ~ 366사이 모든 간선을 capacity가 2가 되게끔 처리
            
            for (int i = 0 ; i <= 365 ; i++) {
                cap[i][i+1] = 2;
                v[i].push_back(i+1);
                v[i+1].push_back(i);
            }
            int ans = 0;
            
            //SPFA
            
            while (true) {
                memset(pre, -1, sizeof(pre));
                memset(inque, false, sizeof(inque));
                fill(dist, dist+367 , inf);
                queue<int> q;
                dist[source] = 0;
                inque[source] = true;
                q.push(source);
                while(!q.empty()){
                    int cur = q.front();
                    inque[cur] = false;
                    q.pop();
                    for (int i = 0 ; i < v[cur].size(); i++) {
                        int next = v[cur][i];
                        if (cap[cur][next] > flow[cur][next] && dist[next] > dist[cur] + cost[cur][next]) {
                            dist[next] = dist[cur] + cost[cur][next];
                            pre[next] = cur;
                            if (inque[next] == false){
                                inque[next] = true;
                                q.push(next);
                            }
                        }
                    }
                }
                if (pre[drain] == -1)
                    break;
                int f = inf;
                for (int i = drain ; i != source ; i = pre[i]) {
                    f = min(f, cap[pre[i]][i] - flow[pre[i]][i]);
                }
                for (int i = drain ; i != source ; i = pre[i]) {
                    flow[pre[i]][i] += f;
                    flow[i][pre[i]] -= f;
                    ans += (f * (cost[pre[i]][i]) * -1);
                }

            }
            printf("%d\n", ans);
            v.clear();
        }














    }

gunwookim 6년 전 0

문제를 해석해야 뭘 도와줄수 있을거같네요...

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

문제

문제

출처

ICPC

MCMF 소스 질문입니다

david1403 6년 전 0

gunwookim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말