$\LARGE{二分图最大权匹配问题}$

给定一张二分图 $G = (V, E)$ ，每一条边从左侧连向右侧，且有一个权值 $w_e$。

要求一个匹配使得边权之和最大，求这个值。

$\LARGE{分析}$

这道题用 $KM$ 算法可以做到时间复杂度 $O(n ^ 3)$

对于每一个左侧点有一个顶标 $lx_i$ ，初始时为 $i$ 连出边中的最大值。

对于每一个右侧点也有一个顶标 $ly_i$ ，初始时为 $0$ 。

在任何时刻，对于一条从 $i$ 连向 $j$ 的边 $e$ ，满足 $lx_i + ly_j \ge w_e$

定义一个原图的子图 $G’$ ，其中的边满足 $lx_i + ly_j = w_e$ ，初始状态下子图由左侧点连出的最大边构成。

若子图 $G’$ 能满足所有左侧点都能找到匹配，那么此图一定为 $G$ 的最大权匹配。

否则，应该模仿匈牙利算法，在增广路上寻找，由于没有最大匹配，所有需要降低某个左侧点的标准。

查询增广路上左侧点的未匹配边权值的最大值即可。

$\LARGE{具体实现}$

在查询增广路时用 $bfs$ ，时间复杂度为 $O(n ^ 3)$ ，用 $dfs$ 则为 $O(n^2 m)$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;
int n, m;
int w[N][N];
int lx[N], ly[N], px[N], py[N], vx[N], vy[N];
int pre[N], slack[N];

void aug(int u) {
    while (u) {
        int k = px[pre[u]];
        px[pre[u]] = u, py[u] = pre[u];
        u = k;
    }
}

void bfs(int s) {
    memset(vx, 0, sizeof vx);
    memset(vy, 0, sizeof vy);
    memset(slack, 0x3f, sizeof slack);
    queue<int> q;
    q.push(s);
    while (1) {
        while (q.size()) {
            int u = q.front();
            vx[u] = 1;
            q.pop();
            for (int i = 1; i <= n; i ++ )
                if (!vy[i]) {
                    if (lx[u] + ly[i] - w[u][i] < slack[i]) {
                        slack[i] = lx[u] + ly[i] - w[u][i];
                        pre[i] = u;
                        if (slack[i] == 0) {
                            vy[i] = 1;
                            if (!py[i]) {aug(i); return;}
                            else q.push(py[i]);
                        }
                    }
                }
        }
        int d = INF;
        for (int i = 1; i <= n; i ++ )
            if (!vy[i])
                d = min(d, slack[i]);
        for (int i = 1; i <= n; i ++ ) {
            if (vx[i]) lx[i] -= d;
            if (vy[i]) ly[i] += d;
            else slack[i] -= d;
        }
        for (int i = 1; i <= n; i ++ )
            if (!vy[i] && slack[i] == 0) {
                vy[i] = 1;
                if (!py[i]) {aug(i); return;}
                else q.push(py[i]);
            }        
    }
}

signed main() {
    scanf("%lld%lld", &n, &m);
    memset(w, 0x8f, sizeof w);
    for (int i = 0; i < m; i ++ ) {
        int u, v, ww;
        scanf("%lld%lld%lld", &u, &v, &ww);
        w[u][v] = max(w[u][v], ww);
        if (ww > lx[u]) lx[u] = ww;
    }
    for (int i = 1; i <= n; i ++ ) bfs(i);
    long long ans = 0;
    for (int i = 1; i <= n; i ++ ) ans += lx[i] + ly[i];
    printf("%lld\n", ans);
    for (int i = 1; i <= n; i ++ ) printf("%lld ", py[i]);
    return 0;
}