先存板子，后面再写讲解

模板：

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
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5 + 400;

ll w[N][N]; // 边权
ll la[N], lb[N], upd[N]; // 左、右部点的顶标
bool va[N], vb[N]; // 访问标记：是否在交错树中
ll match[N]; // 右部点匹配了哪一个左部点
ll last[N]; // 右部点在交错树中的上一个右部点，用于倒推得到交错路
int n;

bool dfs(ll x, ll fa) 
{
    va[x] = 1;
    for(int y = 1; y <= n; y++)
    {
		if(!vb[y])
        {
			if(la[x] + lb[y] == w[x][y]) 
			{ 
                vb[y] = 1; last[y] = fa;
                if(!match[y] || dfs(match[y], y)) 
				{
                    match[y] = x;
                    return true;
                }
            }
            else if(upd[y] > la[x] + lb[y] - w[x][y]) 
			{
                upd[y] = la[x] + lb[y] - w[x][y];
                last[y] = fa;
            }
		}
	}
    return false;
}

ll KM() 
{
    for(int i = 1; i <= n; i++) 
	{
        la[i] = -infll;
        lb[i] = 0;
        for(int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]);
    }
    for(int i = 1; i <= n; i++) 
	{
        memset(va, 0, sizeof(va));
        memset(vb, 0, sizeof(vb));
        for(int j = 1; j <= n; j++) upd[j] = infll;
        // 从右部点st匹配的左部点match[st]开始dfs，一开始假设有一条0-i的匹配
        int st = 0; match[0] = i;
        while(match[st]) 	// 当到达一个非匹配点st时停止
		{ 
            ll delta = infll;
            if(dfs(match[st], st)) break;
            for(int j = 1; j <= n; j++)
                if(!vb[j] && delta > upd[j]) 
				{
                    delta = upd[j];
                    st = j; 		// 下一次直接从最小边开始DFS
                }
            for(int j = 1; j <= n; j++)  // 修改顶标
			{
                if(va[j]) la[j] -= delta;
                if(vb[j]) lb[j] += delta; 
				else upd[j] -= delta;
            }
            vb[st] = true;
        }
        while(st)	// 倒推更新增广路 
		{ 
            match[st] = match[last[st]];
            st = last[st];
        }
    }
	ll ans = 0;
	for(int i = 1; i <= n; i++) 
		if(match[i]) 
			ans += w[match[i]][i];
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	// 根据题目求出 w[][]数组，然后使用KM即可
	
	return 0;
}