带权最大匹配

HDU 2853 Assignment

最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题

唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性

题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值

巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配

再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 (所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目,结果将乱套………………

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;
const int maxn=55;
const int inf=0x3f3f3f3f;
int cnum,mnum;
int linky[maxn],lx[maxn],ly[maxn];
bool visx[maxn],visy[maxn];
int g[maxn][maxn],slack[maxn];

bool dfs(int x)
{
    visx[x]=true;
    for(int y=1;y<=mnum;y++)
    {
        if(visy[y]) continue;
        int t=lx[x]+ly[y]-g[x][y];
        if(t==0)
        {
            visy[y]=true;
            if(linky[y]==-1||dfs(linky[y]))
            {
                linky[y]=x;
                return true;
            }
        }
        else if(slack[y]>t) slack[y]=t;
    }
    return false;
}

int KM()
{
    memset(linky,-1,sizeof linky);
    memset(ly,0,sizeof ly);
    for(int i=1;i<=cnum;i++)
    {
        lx[i]=-inf;
        for(int j=1;j<=mnum;j++)
            if(g[i][j]>lx[i]) lx[i]=g[i][j];
    }
    for(int x=1;x<=cnum;x++)
    {
        for(int i=1;i<=mnum;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=1;i<=mnum;i++)
                if(!visy[i]&&d>slack[i]) d=slack[i];
            for(int i=1;i<=cnum;i++)
                if(visx[i]) lx[i]-=d;
            for(int i=1;i<=mnum;i++)
                if(visy[i]) ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int result=0;
    for(int i=1;i<=mnum;i++)
    {
        if(linky[i]>-1)
            result+=g[linky[i]][i];
    }
    return result;
}

int main()
{
    int eff;
    while(scanf("%d%d",&cnum,&mnum)!=EOF)
    {
        int prenum=0,m;
        for(int i=1;i<=cnum;i++)
            for(int j=1;j<=mnum;j++)
            {
                scanf("%d",&eff);
                g[i][j]=eff*100;
            }
        for(int i=1;i<=cnum;i++)
        {
            scanf("%d",&m);
            prenum+=g[i][m];
            g[i][m]++;
        }
        int ans=KM();
        printf("%d %d\n",cnum-ans%100,ans/100-prenum/100);

    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注