백준22990 사이클

작성일 | In

문제 링크

  • http://icpc.me/22990

사용 알고리즘

  • MCMF

시간복잡도

  • $O(N^4)$

풀이

문제에서 요구하는 결과를 인접 행렬로 나타내보면, 각 행/열마다 한 칸 선택한 형태가 된다는 것을 알 수 있습니다. 그러므로 이 문제는 이분 그래프에서 최소 가중치 완전 매칭을 구하는 문제로 바꿀 수 있습니다. 헝가리안 알고리즘을 사용하면 $O(N^3)$, MCMF를 사용하면 $O(N^4)$에 문제를 해결할 수 있습니다.

전체 코드

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
#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;
constexpr int INF32 = 0x3f3f3f3f;
constexpr ll INF64 = 0x3f3f3f3f3f3f3f3f;

struct Edge{
    ll v, c, f, d, r;
    Edge() = default;
    Edge(ll v, ll c, ll d, ll r) : v(v), c(c), d(d), r(r), f(0) {}
};

int N, M, W[222][222];
vector<Edge> G[444];

void AddEdge(int s, int e, int c, int d){
    G[s].emplace_back(e, c, +d, (int)G[e].size());
    G[e].emplace_back(s, 0, -d, (int)G[s].size()-1);
}

ll D[444];
int P[444], I[444], C[444];
pair<ll, ll> Run(int S, int T){
    ll flow = 0, cost = 0;
    while(true){
        memset(D, 0x3f, sizeof D);
        memset(C, false, sizeof C);
        queue<int> q; q.push(S); D[S] = 0; C[S] = 1;
        while(q.size()){
            int v = q.front(); q.pop(); C[v] = 0;
            for(int i=0; i<G[v].size(); i++){
                const auto &e = G[v][i];
                if(e.c - e.f > 0 && D[e.v] > D[v] + e.d){
                    D[e.v] = D[v] + e.d;
                    P[e.v] = v; I[e.v] = i;
                    if(!C[e.v]) C[e.v] = 1, q.push(e.v);
                }
            }
        }
        if(D[T] == INF64) break;
        ll fl = INF64;
        for(int i=T; i!=S; i=P[i]) fl = min(fl, G[P[i]][I[i]].c - G[P[i]][I[i]].f);
        flow += fl; cost += fl * D[T];
        for(int i=T; i!=S; i=P[i]){
            G[P[i]][I[i]].f += fl;
            G[i][G[P[i]][I[i]].r].f -= fl;
        }
    }
    return {flow, cost};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    memset(W, 0x3f, sizeof W);
    for(int i=1,s,e,x; i<=M; i++) cin >> s >> e >> x, W[s][e] = min(W[s][e], x);

    const int S = 0, T = N << 1 | 1;
    for(int i=1; i<=N; i++){
        AddEdge(S, i, 1, 0);
        AddEdge(N+i, T, 1, 0);
        for(int j=1; j<=N; j++){
            if(W[i][j] != INF32) AddEdge(i, N+j, 1, W[i][j]);
        }
    }
    auto [flow, cost] = Run(S, T);
    if(flow != N){ cout << 0; return 0; }
    cout << "1\n" << cost << "\n";
    for(int i=1; i<=N; i++){
        for(const auto &e : G[i]){
            if(e.f == 1) cout << i << " " << e.v-N << "\n";
        }
    }
}