글 읽기 - 50퍼에서 틀렸다고 하네요..

samgkgkgk 1년 전 0

우선 최소비용 루트를 spfa알고리즘을 활용해서 구한 후에, 최소비용 루트의 반대방향 가중치를 음의 값으로 설정한 후 한번 더 최소비용 루트를 구하고 두 번의 계산을 통해 구한 최소비용을 더한 값을 출력하도록 했습니다. 예제 및 반례는 다 통과하는데 50퍼에서 틀렸다고 하네요 ㅠㅠ

혹시 반례가 있을까요??

########## 해결됐습니다!! ###########

반례가 있더군요..

중복되는 노드를 지나면 안되는데.. 간선이 중복되지 않지만 노드가 중복되는 경우를 고려하지 않았네요 ㅠ

해당 반례입니다!!

7 9
1 2 1
1 3 1
2 4 1
3 4 2
4 5 1
4 6 1
5 7 1
6 7 1
1 7 10

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define _2d_map vector<vector<ll>>
#define _1d_map vector<ll>
#define check vector<bool>
#define INF 9876543210
using namespace std;

ll MCMF(int N, _2d_map& cost, const vector<vector<int>>& capa) {
    ll result = 0;
    vector<vector<int>> flow = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));

    int t = 2;
    //두번 반복
    while(t--) {
        queue<int> q;
        check inQ(N + 1, false);
        vector<int> parent(N + 2, -1);
        _1d_map distance(N + 2, INF);
        q.emplace(1);
        inQ[1] = true;
        distance[1] = 0;

        while(!q.empty()) {
            auto cur = q.front();
            q.pop();
            inQ[cur] = false;

            for(int i = 1; i <= N; i++) {
                if(distance[i] > distance[cur] + cost[cur][i] && capa[cur][i] > flow[cur][i]) {
                    distance[i] = distance[cur] + cost[cur][i];
                    parent[i] = cur;

                    if(!inQ[i]) {
                        inQ[i] = true;
                        q.emplace(i);
                    }
                }
            }
        }

        int f = INF;
        for(int i = N; i != 1; i = parent[i]) {
            f = min(f, capa[parent[i]][i] - flow[parent[i]][i]);
            //이미 지난 루트의 반대방향을 그 루트 가중치의 음의 값으로 설정
            cost[i][parent[i]] = - cost[parent[i]][i];
        }

        for(int i = N; i != 1; i = parent[i]) {
            flow[parent[i]][i] += f;
            flow[i][parent[i]] -= f;
            result += cost[parent[i]][i];
        }
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while(true) {
        int v, e;
        cin >> v >> e;
        if(cin.eof()) break;

        _2d_map cost = _2d_map(v + 1, _1d_map(v + 1, INF));
        vector<vector<int>> capa = vector<vector<int>>(v + 1, vector<int>(v + 1));
        while(e--) {
            int s, v, w;
            cin >> s >> v >> w;
            cost[s][v] = w;
            capa[s][v] = 1;
        }
        cout << MCMF(v, cost, capa) << "\n";
    }
}

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

문제

문제

출처

ICPC

50퍼에서 틀렸다고 하네요..

samgkgkgk 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말