<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Solving Maximum Matching Problem 結報
## OJ AC截圖

## Code

#include <bits/stdc++.h>
#define INF 100000
using namespace std;

bool bellman_ford(int n, int &s, int &t, vector<vector<pair<int, double>>> &edges) {
    vector<double> dis(n, INF);
    vector<int> pi(n, -1);
    dis[s] = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool check = false;
        for (int j = 0; j < n; ++j) {
            for (auto &it : edges[j]) {
                double temp;
                temp = dis[j] + it.second;
                if (dis[it.first] > temp) {
                    dis[it.first] = temp;
                    check = true;
                    pi[it.first] = j;
                }
            }
        }
        if (!check) break;
    }
    if (dis[t] == INF) return false;
    int loc = t;
    while (loc != s) {
        int index = 0;
        for (auto &it : edges[pi[loc]]) {
            if (it.first == loc) {
                edges[loc].push_back({pi[loc], -it.second});
                break;
            }
            ++index;
        }
        edges[pi[loc]].erase(edges[pi[loc]].begin() + index);
        loc = pi[loc];
    }
    return true;
}

double maxMatching(vector<vector<double>> &arr, int &n, int &m) {
    int start = 0, end = m + n + 1;
    vector<vector<pair<int, double>>> adj(n + m + 2, vector<pair<int, double>>());
    for (int i = 1; i <= n; ++i)
        adj[0].push_back({i, 1});
    for (int i = n + 1; i < n + m + 1; ++i)
        adj[i].push_back({end, 1});
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            adj[i].push_back({j + n, arr[i][j]});
    int cnt = n;
    while (cnt--)
        bellman_ford(m + n + 2, start, end, adj);
    double ans = 0;
    stack<int> s;
    for (auto &it : adj[end])
        s.push(it.first);
    while (!s.empty()) {
        int t = s.top();
        s.pop();
        ans -= adj[t][0].second;
    }
    return ans / n;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    while (n && m) {
        vector<vector<double>> arr(n + 1, vector<double>(m + 1, 1));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> arr[i][j];
        cout << fixed << setprecision(2) << maxMatching(arr, n, m) + 0.0000001 << endl;
        cin >> n >> m;
    }
}

### $n$ is the number of bank, $m$ is the number of cruiser
## 空間複雜度分析
* $adj(n * m + n + m)$, $dis(n + m + 2)$, $pi(n + m + 2)$, $s(m)$
* $=n * m + 3 * n + 4 * m + 4$
* $O(n * m)$

## 時間複雜度分析

### Best Case && Worst Case
* 建adj $(n * m + n + m)$
* $n$次bellman
* bellman-ford $O((n + m + 1) * (n * m + n + m))$
* bellman-ford 回追路徑 $O(n * m + 1)$
* $O(n^2m(n+m))$

## DATE
2023/05/21