线性规划 KM算法

有这样一个线性规划问题，求答案以及方案
$$\begin{gathered} MinimizeSatisfy \\ ?\begin{array}{l}{\sum }_{u\in L}{y}_u+{\sum }_{v\in R}{y}_v\\ y_u+y_v\ge w_{u,v}((u,v)\in E)\\ y_u\ge 0\\ y_v\ge 0\end{array} \end{gathered}$$
先无脑对偶再说 (打广告)线性规划和对偶问题_学习笔记
M a x i m i z e S a t i s f y { ∑ ( u , v ) ∈ E w u , v x u , v ∑ v ∈ R x u , v ≤ 1 ∑ u ∈ L x u , v ≤ 1 x u , v ∈ { 0 , 1 } Maximize\ Satisfy\\ \begin{cases} \sum_{(u,v)\in E}w_{u,v}x_{u,v} \\ \sum_{v\in R}x_{u,v}\le1\\ \sum_{u\in L}x_{u,v}\le1\\ x_{u,v}\in\{0,1\} \end{cases} Maximize Satisfy??????????∑(u,v)∈E?wu,v?xu,v?∑v∈R?xu,v?≤1∑u∈L?xu,v?≤1xu,v?∈{ 0,1}?
然后我们敏锐的发现，这个 $x$ 可以看成一个矩阵，两个和式的限制意思就是每一行每一列最多有一个点为 $1$ ，而且若某个点为 $1$ 就会对应有 $w$ 的贡献。

把 $n$ 行 和 $n$ 列看成 $2n$ 个点，把 $x$ 矩阵看成边，为 $1$ 就是对应行和列连边。然后下面这个问题就是个最大权二分图匹配。直接网络流就行了。

然后让我们回到这个问题
$$\begin{gathered} MinimizeSatisfy \\ ?\begin{array}{l}{\sum }_{u\in L}{y}_u+{\sum }_{v\in R}{y}_v\\ y_u+y_v\ge w_{u,v}((u,v)\in E)\\ y_u\ge 0\\ y_v\ge 0\end{array} \end{gathered}$$
考虑如下描述新产生的问题：为二分图上每一个节点设置一个非负的顶标，要求每条边两侧点的顶标之和不小于边权，并且最小化所 有点的顶标和。

令二分图左侧点的顶标为 $xi$ ，右侧点的顶标为 $yi$ 。 我们称一组顶标是合法的，当且仅当其满足了每条边两侧点的顶 标之和不小于边权。对于一组合法的顶标，若边 $(u,v,w)$ 满足 $x_u+y_v=w$ ，则称该边为一条等边。

KM 算法是基于对一组初始时合法的顶标进行调整的算法，由对 偶线性规划的性质，二分图中任意一组合法的匹配的权值和一定不大 于任意一组合法的顶标和，从而若能找到一组由等边构成的完美匹配， 我们就找到了两个问题的一个公共解，因此也是两个问题各自的最优解。

因此，我们希望找到一条由等边构成的增广路。

理解了原理，具体做法就很简单了，每次当等边组成的联通块扩大，然后增广即可。

s_b_CS_DN’s_KATEX

#include <bits/stdc++.h>
#define N 55
using namespace std;
const int inf=1e9;
int n,m,w[N][N],data_x[N],data_y[N];
int vis_x[N],vis_y[N],slack[N],q[N<<1];
int pre[N],rig[N],lef[N];
void BFS(int x){
    int ql=0,qr=0; q[++qr]=x,vis_x[x]=1;while(1){
    while(ql<qr){
    int x=q[++ql];for(int y=1;y<=n;y++){
    if(vis_y[y]) continue;int dif=data_x[x]+data_y[y]-w[x][y];if(dif<=slack[y]){
    pre[y]=x; slack[y]=dif;if(!dif){
    vis_y[y]=1;if(!lef[y]){
    for(;y;lef[y]=pre[y],swap(rig[pre[y]],y));return;}else q[++qr]=lef[y],vis_x[lef[y]]=1;}}}}int val=inf,y;for(int i=1;i<=n;i++)if(!vis_y[i]&&val>slack[i]) y=i,val=slack[i];for(int i=1;i<=n;i++){
    if(vis_x[i]) data_x[i]-=val;if(vis_y[i]) data_y[i]+=val;else slack[i]-=val;}if(!lef[y]){
    for(;y;lef[y]=pre[y],swap(rig[pre[y]],y));return;}else vis_y[y]=vis_x[lef[y]]=1,q[++qr]=lef[y];}
}
void KM(){
    for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)vis_x[j]=vis_y[j]=0,slack[j]=inf;
// cout<<i<<'\n';BFS(i);}
}
int main(){
    
// freopen("matrix.in","r",stdin);
// freopen("matrix.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    cin>>w[i][j];data_x[i]=max(data_x[i],w[i][j]);data_y[j]=max(data_y[j],w[i][j]);}}KM();int res=0;for(int i=1;i<=n;i++) res+=data_x[i]+data_y[i];cout<<res*n<<'\n';if(m)for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    cout<<data_x[i]+data_y[j]<<' ';}cout<<'\n';}
}