글 읽기 - 틀린 이유가 궁금합니다.

wnsgur1714 4년 전 0

기본적인 네트워크 플로우에

maxxx에 각 경로의 최대 유량의 최대를 저장한 뒤 나눴습니다.

그런데 50%정도에 틀렸습니다가 뜨네요.... 제 풀이가 잘못된 건가요?

#include <bits/stdc++.h>
#include <queue>

using namespace std;

const int MAX = 1001;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    for(cin >> t ; t > 0 ; t--){
        vector<int> graph[MAX];
        int pipe[MAX][MAX];
        int npip[MAX][MAX];
        for(int i = 0 ; i < MAX ; i++){
            for(int j = 0 ; j < MAX ; j++){
                pipe[i][j] = 0;
                npip[i][j] = 0;
            }
        }
        int n, ee, a, b;
        cin >> n >> ee >> a >> b;
        for(int i = 0 ; i < ee ; i++){
            int c, d, w;
            cin >> c >> d >> w;
            pipe[c][d] = w;
            graph[c].push_back(d);
            graph[d].push_back(c);
        }
        int value = 0;
        int s = a;
        int e = b;
        int maxxx = 0;
        while(1){
            queue<int> que;
            que.push(s);
            int bumo[MAX];
            fill(bumo, bumo+MAX, -1);
            while(!que.empty() && bumo[e] == -1){
                int now = que.front();
                que.pop();
                for(int i : graph[now]){
                    if(bumo[i] == -1 && pipe[now][i] - npip[now][i] > 0){
                        bumo[i] = now;
                        if(i == e){
                            break;
                        }
                        que.push(i);
                    }
                }
            }
            if(bumo[e] == -1){
                break;
            }
            int mix = 1000000000;
            int maxx = 1000000000;
            for(int i = e ; i != s ; i = bumo[i]){
                maxx = min(maxx, pipe[bumo[i]][i] - npip[bumo[i]][i]);
                mix = min(mix, pipe[bumo[i]][i]);
            }
            value += maxx;
            maxxx = max(maxxx, mix);
            for(int i = e ; i != s ; i = bumo[i]){
                npip[bumo[i]][i] += maxx;
                npip[i][bumo[i]] -= maxx;
            }
        }
        cout.precision(4);
        cout << value/(double)maxxx;
    }
}

pichulia 4년 전 0

maxxx 값은 flow를 써서 구할 수 없을듯 합니다.

예를 들어 s --> 1 --> {2,3,4} --> e 이런 그래프가 있을 때

(1과2, 1과3, 1과4 가 연결되있고 2,3,4가 e랑 연결되있는 상황)

s-->1 유량이 6

1 --> 2 유량이 4

1--> 3 유량이 4

1 --> 4 유량이 5

뭐 이런식인 경유

s-->1-->4-->e 길을 사용하는 것이 최대이지만

maxflow 계산을 위해선 1-->2, 1-->3-->e 만 확인하면 충분하기 때문에

1-->4 라는 길을 확인하지 못하게 됩니다.

wnsgur1714 4년 전 0

한번에 이해가 되네요.... 감사합니다!

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

문제

문제

출처

ICPC

틀린 이유가 궁금합니다.

wnsgur1714 4년 전 0

pichulia 4년 전 0

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말