训练指南 UVA - 11383（KM算法的应用 lx+ly >=w(x,y)）

---

layout: post

title: 训练指南 UVA - 11383（KM算法的应用 lx+ly >=w(x,y)）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- KM算法

- 训练指南

---

Golden Tiger Claw

UVA - 11383

题意

给一个n*n的矩阵，每个格子中有正整数w[i[j]，试为每行和每列分别确定一个数字row[i]和col[i]，使得任意格子w[i][j]<=row[i]+col[j]恒成立。先输row，再输出col，再输出全部总和（总和应尽量小）。

思路

本题与匹配无关，但可以用KM算法解决。

　　KM算法中的顶标就是保持了Lx[i]+ly[j]>=g[i[j]再求最大权和匹配的，但这个最大权和并没有关系。我们可以将row[i]看成一个男的，col[i]看成一个女的，这样男女的总数就相等。

　　一般来说，Lx[i]或Ly[i]仅需要取该行/列中最大的那个数即可保证满足要求，但是这样太大了，可以通过调整来使得总和更小。而KM算法的过程就是一个调整的过程，每一对匹配的男女的那条边的权值就会满足等号 wi[j]=row[i]+col[j]，至少需要一个来满足等号，这样才能保证row[i]+col[j]是达到最小的，即从j列看，col[j]满足条件且最小，从i行看，row[i]满足条件且最小。这刚好与KM算法求最大权和一样。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=5e2+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

int g[530][530];  ///存图

int nx,ny; /// 两边点数

bool visx[maxn],visy[maxn];

int slack[maxn];

int linker[maxn];   ///y中各点匹配状态

int lx[maxn],ly[maxn]; /// x,y中的点标号

bool dfs(int x){

    visx[x]=true;

    for(int y=0;y<ny;y++){

        if(visy[y])continue;

        int tmp=lx[x]+ly[y]-g[x][y];

        if(tmp==0){

            visy[y]=true;

            if(linker[y]==-1||dfs(linker[y])){

                linker[y]=x;return true;

            }

        }

        else if(slack[y]>tmp)slack[y]=tmp;

    }

    return false;

}

int KM(){

    memset(linker,-1,sizeof(linker));

    memset(ly,0,sizeof(ly));

    for(int i=0;i<nx;i++){

        lx[i]=-inf;

        for(int j=0;j<ny;j++){

            if(g[i][j]>lx[i])lx[i]=g[i][j];

        }

    }

    for(int x=0;x<nx;x++){

        for(int i=0;i<ny;i++)slack[i]=inf;

        while(true){

            memset(visx,false,sizeof(visx));

            memset(visy,false,sizeof(visy));

            if(dfs(x))break;

            int d=inf;

            for(int i=0;i<ny;i++)

                if(!visy[i]&&d>slack[i])d=slack[i];

            for(int i=0;i<nx;i++)

                if(visx[i])lx[i]-=d;

            for(int i=0;i<ny;i++)

                if(visy[i])ly[i]+=d;

                else slack[i]-=d;

        }

    }

    int res=0;

    for(int i=0;i<ny;i++)

        if(linker[i]!=-1)res+=g[linker[i]][i];

    return res;

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    while(cin>>n){

        nx=ny=n;

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)cin>>g[i][j];

        int ans=KM();

        cout<<lx[0];

        for(int i=1;i<n;i++)cout<<" "<<lx[i];cout<<endl;

        cout<<ly[0];

        for(int i=1;i<n;i++)cout<<" "<<ly[i];cout<<endl;

        cout<<ans<<endl;

    }

    return 0;

}