Bookmarks

You haven't yet saved any bookmarks. To bookmark a post, just click .

  • Getting Confidence (MCMF)

  • MCMF经典题,将行列聚成点建图,由于计算的是连乘积,用取对数的方法把乘法变成加法作为流量建图计算

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int INF = 0x7fffffff;
    const int maxn = 1e5 + 50;
    const double INFF = 1.0 * 1e18;
    struct MEdge {
        int from, to, cap;
        double cost;
        MEdge(int from, int to, int cap, double cost)
            : from(from), to(to), cap(cap), cost(cost) {}
    };
    
    struct MCMF { // qdd tql
        int n, s, t, flow;
        double cost;
        vector<MEdge> es;
        vector<vector<int>> G;
        vector<double> d;
        vector<int> p, a; // dis, prev, add
        deque<bool> in;
    
        MCMF(int n, int s, int t)
            : n(n), s(s), t(t), flow(0), cost(0.0), G(n + 1), p(n + 1), a(n + 1) {}
    
        void add_edge(int u, int v, int cap, double cost) {
            G[u].push_back(es.size());
            es.emplace_back(u, v, cap, cost);
            G[v].push_back(es.size());
            es.emplace_back(v, u, 0, -cost);
        }
    
        bool spfa() {
            d.assign(n + 1, INFF);
            in.assign(n + 1, false);
            d[s] = 0;
            in[s] = 1;
            a[s] = INF;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                in[u] = false;
                for (int &i : G[u]) {
                    MEdge &e = es[i];
                    if (e.cap && d[e.to] > d[u] + e.cost) {
                        d[e.to] = d[u] + e.cost;
                        p[e.to] = i;
                        a[e.to] = min(a[u], e.cap);
                        if (!in[e.to]) {
                            q.push(e.to);
                            in[e.to] = true;
                        }
                    }
                }
            }
            return d[t] != INFF;
        }
    
        void solve() {
            while (spfa()) {
                flow += a[t];
                cost += a[t] * d[t];
                int u = t;
                while (u != s) {
                    es[p[u]].cap -= a[t];
                    es[p[u] ^ 1].cap += a[t];
                    u = es[p[u]].from;
                }
            }
        }
    };
    
    int ma[105][105];
    int main() {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> ma[i][j];
            }
        }
        int s = 0;
        int tot = n * (n + 2) + 2;
        int t = tot - 1;
        MCMF mc = MCMF(tot, s, t);
        for (int i = 1; i <= n; i++) {
            mc.add_edge(s, n * n + i, 1, 0.0);
        }
        for (int i = 1; i <= n; i++) {
            mc.add_edge(n * n + n + i, t, 1, 0.0);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                mc.add_edge(n * n + i, n * (j - 1) + i, 1, 0.0);
                mc.add_edge(n * (j - 1) + i, n * n + n + j, 1, -log10(ma[j][i]));
            }
        }
        mc.solve();
        for (int i = n * n + 1; i <= n * n + n; i++) {
            for (auto ii : mc.G[i]) {
                MEdge e = mc.es[ii];
                if (e.cap == 0) {
                    if (i == n * n + n)
                        cout << (e.to - 1) / n + 1;
                    else
                        cout << (e.to - 1) / n + 1 << " ";
                }
            }
        }
    }