1. 把左边每个点的顶标设为与它相连的边中最大的权值，右边每个点顶标设为\(0\)。
2. 对于每个点\(i\)，进行步骤\(3\)。
3. 在与\(i\)相连的所有边中找到一条边\((i,u)\)使得\(w(i,u)=val(i)+val(u)\)，如果\(u\)未匹配则匹配\(i\)和\(u\)，进入步骤\(4\)；如果\(u\)已匹配则对\(u\)重复步骤\(3\)。都找完后进入步骤\(4\)。
4. 若找到了满足条件的点\(u\)，则匹配\(i\)和\(u\),重复步骤\(2\)。若没有找到，进入步骤\(5\)。
5. 把上次的\(3\)操作中涉及的所有左边点顶标\(-1\)，右边点顶标\(+1\)，重复步骤\(3\)。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,e;
int array[1001][1001];//邻接存图
int match[1001];//匹配
int value_left[1001];//左点顶标
int value_right[1001];//右点顶标
int visit_left[1001];//左点标记
int visit_right[1001];//右点标记
int ans;
inline int read(){//快读
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int augment(int x){//增广操作(步骤3)
visit_left[x]=1;//给涉及的点打标记
for(int i=1;i<=m;i++){//遍历每一条边
if(!visit_right[i]&&value_right[i]+value_left[x]==array[x][i]){//如果i此次未被涉及过且满足条件
visit_right[i]=1;//涉及i
if(match[i]==-1||augment(match[i])){//如果i未被匹配
match[i]=x;//把i与x匹配
return 1;//返回成功
}
}
}
return 0;//如果一个都不行，返回失败
}
int main(){
memset(match,-1,sizeof match);
n=read();
m=read();
e=read();
for(int i=1;i<=e;i++){
int u,v,w;
u=read();
v=read();
w=read();
array[u][v]=w;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){//处理左点顶标
value_left[i]=max(value_left[i],array[i][j]);
}
}
for(int i=1;i<=n;i++){//每次记得清空标记
memset(visit_left,0,sizeof visit_left);
memset(visit_right,0,sizeof visit_right);
while(!augment(i)){//对于一个点如果增广不成功就不停重复
for(int j=1;j<=n;j++){//如果左点被访问则-1
value_left[j]-=visit_left[j];
}
for(int j=1;j<=m;j++){//如果右点被访问则+1
value_right[j]+=visit_right[j];
}
memset(visit_left,0,sizeof visit_left);
memset(visit_right,0,sizeof visit_right);
}
}
for(int i=1;i<=m;i++){//统计匹配的答案
if(match[i]!=-1)ans+=array[match[i]][i];
}
cout<<ans;
return 0;
}
原文：https://www.cnblogs.com/xiong-6/p/11391575.html