[传送门](https://www.luogu.com.cn/problem/P6577)
题目让我们找最大权值的完美匹配，注意是完美匹配的情况下，边权最大。
由于节点的数量非常少，所以可以直接开一个数组维护边权。开一个二维数组将边的初始信息存入。
每个节点进行匹配，将当前点加进来后，遍历整张图边的最大值，记录，接着次大值……直到没有增广路了结束。一路上节点要记录是从哪个节点增广来的，最后要换配（更新匹配的节点），因为最后还要输出匹配的编号。
### 代码思路
- 初始化，读入基本信息。
- 将每个节点进行匹配。
- 找到图上当前的最大边权。
- 根据最大边权，处理增广路。
- 去掉最大权值的边，继续找最大边权，重复上一步。
- 统计权值，输出。
### 代码
```cpp
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const long long o_o=1e3+10;
const long long m_a=1e18;
long long n,m;
long long m_p[o_o][o_o];//建立点点之间的边权
long long b_d[o_o];//存储匹配的编号
long long s_s[o_o];//到节点的最小值
long long p_r[o_o];//记录增广的节点（从那个点来的）
long long m_x[o_o];//匹配点集权值
long long m_y[o_o];//被匹配点集权值
bool b_b[o_o];//标记是否遍历过
void f_i(long long u){
//初始化
long long k_k=0;//记录当前处理的节点的编号
long long l_t=0;//记录最优路径的编号
long long x,m_i;//当前处理的节点，最小值
memset(p_r,0,sizeof(p_r));//初始化
for(long long i=1;i<=n;i++)s_s[i]=m_a;//初始化
b_d[0]=u;//从当前节点开始
while(1){
x=b_d[k_k];//找到匹配的节点
m_i=m_a;//初始化最小值
b_b[k_k]=1;//标记
for(long long i=1;i<=n;i++){//枚举所有被匹配的节点
if(b_b[i])continue;//被标记过
if(s_s[i]>m_x[x]+m_y[i]-m_p[x][i]){//更新最小值
//这里边的权值取的是相反数，所以权值越大，值越小
s_s[i]=m_x[x]+m_y[i]-m_p[x][i];//更新最小值
p_r[i]=k_k;//记录来的点
}
if(s_s[i]<m_i){
m_i=s_s[i];//更新最小值
l_t=i;//记录编号
}
}
for(long long i=0;i<=n;i++){//枚举所有节点
if(b_b[i]){//标记过的节点
m_x[b_d[i]]-=m_i;//匹配节点加上最大边权
m_y[i]+=m_i;//被匹配节点减去最大边权
}else s_s[i]-=m_i;//所有节点加上最大边权
//加上最大边权，下次的边权一定小于等于这个边权，可以继续找次大边权
}
k_k=l_t;//处理记录的编号最优边的增广路
if(b_d[k_k]==-1)break;//没有增广路，退出循环
}
while(k_k){//回溯（换配）
b_d[k_k]=b_d[p_r[k_k]];//更新匹配编号
k_k=p_r[k_k];//往回找
}
}
long long k_m(){
//初始化
memset(b_d,-1,sizeof(b_d));//未匹配过的节点的值是 -1
memset(m_x,0,sizeof(m_x));
memset(m_y,0,sizeof(m_y));
for(long long i=1;i<=n;i++){
memset(b_b,0,sizeof(b_b));//清空标记
f_i(i);//匹配 i 节点
}
long long r_s=0;
for(long long i=1;i<=n;i++)
if(b_d[i]!=-1)r_s+=m_p[b_d[i]][i];//统计权值
return r_s;
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)m_p[i][j]=-m_a;//初始化
for(long long i=1;i<=m;i++){
long long u=r_r(),v=r_r(),w=r_r();
m_p[u][v]=w;//边赋权值
}
printf("%lld\n",k_m());//计算最大权值
for(long long i=1;i<=n;i++)//输出匹配结果
printf("%lld ",b_d[i]);
puts("");
return 0;
}
```