글 읽기 - 디닉 알고리즘으로 풀어봤는데, 31%쯤에서 '틀렸습니다'를 받네요..

redpigeon 3년 전 0

디닉 알고리즘으로 코드를 작성해봤습니다.

일반적인 네트워크 유량 문제처럼 접근하되,

1) 네트워크에 가장 작은 용량을 가진 엣지부터 하나씩 추가하면서

2) 디닉 알고리즘으로 네트워크 유량을 계산하고,

3) 이때 전체 유량과 일치하는 가장 최소값...이 등장하면 정답이 되게끔 구현했습니다.

31%까지 올라가는걸 보니 대충 로직은 맞는 것 같은데...

대체 무엇을 놓치고 있는걸까요?ㅠㅠㅠ

변수 선언 사이즈가 틀린건가 싶어서 이래저래 수정해 보고.. 며칠째 찔끔찔끔 고쳐서 제출해보고..만 반복하고 있네요..

알고나니 그렇게 어려운 문제는 아닌 것 같은데, 왜 자꾸 중간에 틀리는지 모르겠습니다..ㅠㅠㅠ

이제 부끄러워서 제출도 더이상 못하겠어요ㅠㅠㅠㅠㅠㅠㅠ

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <tuple>

#define INF 1e18

using namespace std;

typedef long long ll;
typedef tuple<ll, int, int> Conn;

struct Dinic {
    ll n;
    
    struct Edge {
        ll v, cap, rev;
        Edge(ll v, ll cap, ll rev): v(v), cap(cap), rev(rev) {}
    };

    vector<vector<Edge>> vt;
    void addEdge(ll s, ll e, ll c) {
        vt[s].emplace_back(e, c, vt[e].size());
        vt[e].emplace_back(s, 0, vt[s].size()-1);
    }

    vector<ll> level, work;
    Dinic(ll n): n(n) {
        vt.resize(n+1);
        level.assign(n+1, -1);
        work.assign(n+1, 0);
    }

    bool bfs(ll src, ll sink) {
        level.assign(n+1, -1);
        queue<ll> qu;
        level[src] = 0;
        qu.push(src);
        while (qu.size()) {
            ll here = qu.front();
            qu.pop();
            for (auto i: vt[here]) {
                if (i.cap>0 && level[i.v] == -1) {
                    level[i.v] = level[here] + 1;
                    qu.push(i.v);
                }
            }
        }

        return level[sink] != -1;
    }

    ll dfs(ll sink, ll here, ll crtcap) {
        if (sink == here) {
            return crtcap;
        }

        for (ll &i=work[here]; i<vt[here].size(); i++) {
            ll cap = vt[here][i].cap;
            ll there = vt[here][i].v;
            if (level[here]+1 == level[there] && cap>0) {
                ll limit = dfs(sink, there, min(crtcap, cap));
                if (limit) {
                    vt[here][i].cap -= limit;
                    vt[there][vt[here][i].rev].cap += limit;

                    return limit;
                }
            }
        }

        return 0;
    }

    ll solve(ll src, ll sink) {
        ll max_flow = 0;
        while (bfs(src, sink)) {
            work.assign(n+1, 0);
            while (1) {
                ll path_flow = dfs(sink, src, INF);
                if (!path_flow) {
                    break;
                }

                max_flow += path_flow;
            }
        }

        return max_flow;
    }
};

ll F, P, current[202], limit[202], total;

int main() {
    scanf("%lld%lld", &F, &P);
    for (ll i=1; i<=F; i++) {
        scanf("%lld%lld", &current[i], &limit[i]);
        total += current[i];
    }

    ll cost[202][202];
    for (int i=0; i<202; i++) {
		for(int j=0; j<202; j++) {
			cost[i][j] = (i==j?0:INF);
		}
	}

    for (ll i=0; i<P; i++) {
        ll A, B, T;
        scanf("%lld%lld%lld", &A, &B, &T);

        cost[A][B] = min(T, cost[A][B]);
        cost[B][A] = min(T, cost[B][A]);
    }

    for (ll i=1; i<=F; i++) {
        for (ll j=1; j<=F; j++) {
            for (ll k=1; k<=F; k++) {
                cost[j][k] = (j==k)?0:min(cost[j][k], cost[j][i]+cost[i][k]);
            }
        }
    }

    vector<Conn> edges;
	for (int i=1; i<=F; i++) {
		for (int j=i+1; j<=F; j++) {
			if (cost[i][j] < INF) {
				edges.push_back(Conn(cost[i][j], i, j));
			}
		}
	}

    sort(edges.begin(), edges.end());

    Dinic d(1+F+F+1);

    for (ll i=1; i<=F; i++) {
        d.addEdge(0, i, current[i]);
        d.addEdge(i+F, F+F+1, limit[i]);
    }

    ll result = 0;
    ll max_flow = 0;

    for (int k=0; k<edges.size(); k++) {
        int i, j;
        tie(result, i, j) = edges[k];

        d.addEdge(i, j+F, INF);
        d.addEdge(j, i+F, INF);

        max_flow += d.solve(0, F+F+1);
        if (max_flow == total) {
            printf("%lld\n", result);
            return 0;
        }
    }

    printf("-1\n");
    return 0;
}

pichulia 3년 전 1

i 에서 i+F 로 가는 간선도 추가해주세요.

1
3
3
4
2 21474

// answer : 0

redpigeon 3년 전 0

와.... 이걸 놓치고 있었군요..ㄷㄷㄷㄷㄷㅠㅠㅠㅠㅠ

이런 기본적인 것도 놓치다니ㅠㅠ네트워크 유량에 대해서 아직 익숙하지 않은가 봅니다ㅠㅠㅠㅠ

덕분에 며칠간의 삽질이 드디어 완료되었네요ㅠㅠㅠㅠㅠㅠㅠ

감사합니다!!!! 많이 배워갑니다!!!!!

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

문제

문제

출처

ICPC

디닉 알고리즘으로 풀어봤는데, 31%쯤에서 '틀렸습니다'를 받네요..

redpigeon 3년 전 0

pichulia 3년 전 1

redpigeon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말