【KM算法】UVA 11383 Golden Tiger Claw

题目大意

给你一个\(n×n\)的矩阵G，每个位置有一个权，求两个一维数组\(row\)和\(col\)，使\(row[i] + col[j]\ge G[i][j]\)，并且\(∑row+∑col\)最小，输出这个和。

样例输入

2

1 1

1 1

数据范围

\(0\le N\le 500\)

样例输出

1 1

0 0

2

思路

题面花里胡哨，其实就是二分图带权匹配，求的数组其实就是KM算法里的顶标。就是模板啊！这也太水了。

代码

#include <cstdio>

#include <cstring>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=500+10;

int n;

int g[maxn][maxn];

int match[maxn],wx[maxn],wy[maxn],slack[maxn];

bool visx[maxn],visy[maxn];

bool dfs(int u){

    visx[u]=true;

    for(int v=1;v<=n;v++){

        if(!visy[v]){

            int t=wx[u]+wy[v]-g[u][v];

            if(t==0){

                visy[v]=true;

                if(match[v]==-1||dfs(match[v])){

                    match[v]=u;

                    return true;

                }

            }

        else if(slack[v]>t)slack[v]=t;

        }

    }

    return false;

}

int KM(){

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

    memset(wx,0,sizeof(wx));

    memset(wy,0,sizeof(wy));

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

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

        }

    }

    for(int x=1;x<=n;x++){

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

            slack[i]=INF;

        while(1){

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

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

            if(dfs(x))break;

            int minz=INF;

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

               if(!visy[i]&&minz>slack[i])

                    minz=slack[i];

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

               if(visx[i])wx[i]-=minz;

            for(int i=1;i<=n;i++){

                if(visy[i])wy[i]+=minz;

                else slack[i]-=minz;

            }

        }

    }

    int ans=0;

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

       ans+=wx[i]+wy[i];

    return ans;

}

int main(){

    while(~scanf("%d",&n)){

        memset(g,0,sizeof(g));

        for(int i=1;i<=n;i++){

            for(int j=1;j<=n;j++){

                scanf("%d",&g[i][j]);

            }

        }

        int ans=KM();

        printf("%d",wx[1]);

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

            printf(" %d",wx[i]);

        printf("\n");

        printf("%d",wy[1]);

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

            printf(" %d",wy[i]);

        printf("\n");

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

【KM算法】UVA 11383 Golden Tiger Claw

题目大意

样例输入

数据范围

样例输出

思路

代码

最新文章

热门文章