백준14283 간선 이어가기

작성일 | In

문제 링크

  • http://icpc.me/14283

사용 알고리즘

  • Min Cut

풀이

$S$와 $T$가 연결되는 시점이란, $S$와 $T$가 연결되어 있지 않은 상태에서, 두 컴포넌트를 연결하는 간선이 추가되는 시점을 의미합니다. 즉, $S$-$T$ Cut에서 간선 하나를 추가한 것을 의미합니다.

어떤 간선 $e = (u, v)$가 있어서, $e$를 제거한 그래프에서 S-T Min Cut을 구했을 때 $u, v$가 서로 다른 컴포넌트에 포함되었다면 $e$는 정답이 될 수 있는 후보입니다. 즉, 모든 간선에 대해 해당 간선을 제거하고 Min Cut을 구한 다음, 양 끝 정점이 서로 다른 컴포넌트에 속한다면 정답을 갱신해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

template<typename FlowType, size_t _Sz, FlowType _Inf=1'000'000'007>
struct Dinic{
    struct Edge{ int v, dual; FlowType c; };
    int Level[_Sz], Work[_Sz];
    vector<Edge> G[_Sz];
    void clear(){ for(int i=0; i<_Sz; i++) G[i].clear(); }
    void AddEdge(int s, int e, FlowType x){
        G[s].push_back({e, (int)G[e].size(), x});
        G[e].push_back({s, (int)G[s].size()-1, x});
    }
    bool BFS(int S, int T){
        memset(Level, 0, sizeof Level);
        queue<int> Q; Q.push(S); Level[S] = 1;
        while(Q.size()){
            int v = Q.front(); Q.pop();
            for(const auto &i : G[v]){
                if(!Level[i.v] && i.c) Q.push(i.v), Level[i.v] = Level[v] + 1;
            }
        }
        return Level[T];
    }
    FlowType DFS(int v, int T, FlowType tot){
        if(v == T) return tot;
        for(int &_i=Work[v]; _i<G[v].size(); _i++){
            Edge &i = G[v][_i];
            if(Level[i.v] != Level[v] + 1 || !i.c) continue;
            FlowType fl = DFS(i.v, T, min(tot, i.c));
            if(!fl) continue;
            i.c -= fl;
            G[i.v][i.dual].c += fl;
            return fl;
        }
        return 0;
    }
    FlowType MaxFlow(int S, int T){
        FlowType ret = 0, tmp;
        while(BFS(S, T)){
            memset(Work, 0, sizeof Work);
            while((tmp = DFS(S, T, _Inf))) ret += tmp;
        }
        return ret;
    }
    tuple<FlowType, vector<int>, vector<int>, vector<pair<int, int>>> MinCut(int S, int T){
        FlowType fl = MaxFlow(S, T);
        vector<int> a, b;
        vector<pair<int, int>> edges;
        const int Bias = 1e9;
        queue<int> Q; Q.push(S); Level[S] += Bias;
        while(Q.size()){
            int v = Q.front(); Q.pop();
            for(const auto &i : G[v]){
                if(!Level[i.v]) edges.emplace_back(v, i.v);
                else if(Level[i.v] < Bias) Q.push(i.v), Level[i.v] += Bias;
            }
        }
        for(int i=0; i<_Sz; i++){
            if(Level[i]) a.push_back(i);
            else b.push_back(i);
        }
        return make_tuple(fl, a, b, edges);
    }
};

int N, M, Sum, S[1010], E[1010], X[1010], Source, Sink;
Dinic<int, 51> Flow;

int Solve(int del){
    Flow.clear();
    for(int i=1; i<=M; i++) if(i != del) Flow.AddEdge(S[i], E[i], X[i]);
    auto [flow,u,v,edge] = Flow.MinCut(Source, Sink);
    bool s = find(all(v), S[del]) != v.end();
    bool e = find(all(v), E[del]) != v.end();
    if(s == e) return -1;
    return Sum - flow;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++) cin >> S[i] >> E[i] >> X[i], Sum += X[i];
    cin >> Source >> Sink;
    int mx = 0;
    for(int i=1; i<=M; i++) mx = max(mx, Solve(i));
    cout << mx;
}