<题目链接>
题目大意：
给出n个点m条单向边边以及经过每条边的费用，让你求出走过一个哈密顿环（除起点外，每个点只能走一次）的最小费用。题目保证至少存在一个环满足条件。
解题分析：
因为要求包含所有点一次的环，我们不难发现，这个环中的每个点的出度和入度均为1，所以我们不妨将每个点进行拆点，将所有点的出度和入度分为两部分。因为该环需要包括所有的点，并且题目需要求该环的最小权值，相当于该带权二分图的每个点都需要被覆盖到，由于本题就转化为求该二分图的最优完美匹配问题。二分图的最优匹配问题求解，我们会想到KM算法，但是KM是求最大权完美匹配，所以我们对每个边的权值全部取反，这时候求出的最大权值(该权值<0)的相反数就是最小权值的完美匹配了。
BFS版：
#include <bits/stdc++.h>
using namespace std; typedef long long ll; #define RP(i, s, t) for (int i = s; i <= t; i++)
#define clr(a, b) memset(a, b, sizeof(a)) const int N = ;
const ll INF = 1e18; ll n, wx[N], wy[N], match[N], g[N][N], slk[N], pre[N];
bool viy[N]; void BFS(ll k) {
ll py = , px, yy = , cur;
match[py] = k;
clr(slk, 0x3f); clr(pre, );
do {
px = match[py];
cur = INF;
viy[py] = ;
RP(i, , n)
if (!viy[i]) {
if (wx[px] + wy[i] - g[px][i] < slk[i]) {
slk[i] = wx[px] + wy[i] - g[px][i];
pre[i] = py;
}
if (slk[i] < cur) {
cur = slk[i];
yy = i;
}
}
for (int i = ; i <= n; ++i) {
if (viy[i]) {
wx[match[i]] -= cur;
wy[i] += cur;
} else
slk[i] -= cur;
}
py = yy;
} while (match[py] != ); while (py) {
match[py] = match[pre[py]];
py = pre[py];
}
}
ll KM() {
RP(i, , n) {
wx[i] = , wy[i] = , match[i] = ;
RP(j, , n) wx[i] = max(wx[i], g[i][j]);
}
RP(i, , n) {
clr(viy, );
BFS(i);
}
ll ans = ;
RP(i, , n) ans += wx[match[i]] + wy[i];
return ans;
} int main() {
int T, m, u, v, c;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
RP(i, , n) RP(j, , n) g[i][j] = -INF;
//将每个点进行拆点，分成出度(x部分)和入度(y部分)两部分来处理
RP(i, , m) {
scanf("%d%d%d", &u, &v, &c);
if (g[u][v] < -c) //因为要求最小的权值，而KM算法是求最大的权值，所以这里将所有边的权值取反,这样用KM算出的最大值的相反数就是最小值了
g[u][v] = -c; //去重边，取权值最小的边
}
printf("%lld\n", - * KM()); //对求出的最大值取反即可
}
}
DFS版：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N =;
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define INF 0x3f3f3f3f
int n,linker[N],w[N][N],lx[N],ly[N],slack[N];
int visx[N],visy[N],nx,ny;
bool DFS(int x){
visx[x]=;
rep(y,,n){
if(visy[y]==)continue; //每次只常识匹配一次y，相当于匈牙利中的vis[]
int tmp=lx[x]+ly[y]-w[x][y]; //x,y期望值之和与x,y之间的权值的差值
if(!tmp){ //x,y之间期望值==他们之间权值时符合要求
visy[y]=;
if(linker[y]==-||DFS(linker[y])){ //y没有归属者，或者y的原始归属者能够找到其他归属者
linker[y]=x;
return true;
}
}else slack[y]=min(slack[y],tmp);
}
return false;
}
int KM(){
mem(linker,-);mem(ly,); //初始化，y的期望值为0
rep(i,,nx){ //初始化lx[]数组
lx[i]=-INF;
for(int j=;j<=ny;j++){
lx[i]=max(lx[i],w[i][j]); //lx为x的期望值,lx初始化为与它关联边中最大的
}
}
//为每一个x尝试解决归属问题
rep(x,,n){
rep(i,,n)slack[i]=INF;
while(true){
mem(visx,);mem(visy,);
if(DFS(x))break;//若成功（找到了增广轨），则该点增广完成，进入下一个点的增广
//若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。
//方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，
//所有在增广轨中的Y方点的标号全部加上一个常数d
int d=INF;
rep(i,,ny)if(!visy[i])d=min(d,slack[i]); //d为没有匹配到的y的slack中的最小值
rep(i,,nx)if(visx[i])lx[i]-=d;
rep(i,,ny)
if(visy[i])ly[i]+=d;
else slack[i]-=d; //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d
}
}
int res=;
rep(i,,ny){
if(linker[i]!=-)
res+=w[linker[i]][i];
}
return res;
}
/*-- 以上为KM算法模板 --*/
int main(){
int T,m,u,v,c;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
rep(i,,n) rep(j,,n){
w[i][j]=-INF;
}
//将每个点进行拆点，分成出度(x部分)和入度(y部分)两部分来处理
nx=ny=n;
rep(i,,m){
scanf("%d%d%d",&u,&v,&c);
if(w[u][v]<-c) //因为要求最小的权值，而KM算法是求最大的权值，所以这里将所有边的权值取反,这样用KM算出的最大值的相反数就是最小值了
w[u][v]=-c; //去重边，取权值最小的边
}
printf("%d\n",-*KM()); //对求出的最大值取反即可
}
}