hdu 2853

虛擬賽一開始lyf就對我說這是一道匹配的題目，我一看明顯裸的最優匹配，敲完提交wrong，

題目要求改變盡量少的公司，就是如果遇到相等的權值，優先選擇跟他原來匹配的，KM匹配是按序號大小來的，如果一個公司原來匹配的序號較大，前面有權值相等的點時，KM就會選擇前面的點參加匹配。想了好長時間不知道怎麼去優先選擇原來匹配的邊，

最後想著如果把原來匹配的邊變得大一些的話，就可以，但是變大的話就會影響最優匹配的總值，而且變大的話還會影響原來比他大的權值，所以就是所有的權值都得擴大，我想到的是都*100，原來匹配的邊再加1，因為最多選50條邊，也就是最多有50個01相加，不會超過一百，得到的答案除以一百，就把加的1都去掉了，只要擴大的倍數大於n就可以，，

#include<stdio.h>
#include<string.h>
#define N 55
#define inf 0x3fffffff
int map[N][N],lx[N],ly[N],sx[N],sy[N],d[N],n,m,match[N],Kmatch[N],tch[N];
int find(int x)
{
    sx[x]=1;
    for(int i=1;i<=m;i++)
    {
        if(sy[i]==1)continue;
        int temp=lx[x]+ly[i]-map[x][i];
        if(temp==0)
        {
            sy[i]=1;
            if(match[i]==-1||find(match[i])==1)
            {
                match[i]=x;
                Kmatch[x]=i;
                return 1;
            }
        }
        else d[i]=d[i]>temp?temp:d[i];
    }
    return 0;
}
int KM()
{
    int i,j,k,min,sum;
    memset(ly,0,sizeof(ly));
    memset(match,-1,sizeof(match));
    memset(Kmatch,-1,sizeof(Kmatch));
    for(i=1;i<=n;i++)
    {
        lx[i]=map[i][1];
        for(j=2;j<=m;j++)
            if(lx[i]<map[i][j])
                lx[i]=map[i][j];
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            d[j]=inf;
        while(1)
        {
            memset(sx,0,sizeof(sx));
            memset(sy,0,sizeof(sy));
            if(find(i)==1)break;
            min=inf;
            for(k=1;k<=m;k++)
                if(sy[k]==0&&min>d[k])
                    min=d[k];
            for(j=1;j<=n;j++)
                if(sx[j]==1)lx[j]-=min;
            for(j=1;j<=m;j++)
                if(sy[j]==1)ly[j]+=min;
        }
    }
    sum=0;
    for(i=1;i<=n;i++)
        sum+=map[i][Kmatch[i]];
    return sum;
}
int main()
{
    int i,j,k,ans,sum;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                map[i][j]=-inf;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                map[i][j]*=100;
            }
        ans=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&k);
            tch[i]=k;
            ans+=map[i][k];
            map[i][k]++;
        }
        ans/=100;
        sum=KM()/100;
        k=0;
        for(i=1;i<=n;i++)
            if(tch[i]!=Kmatch[i])
                k++;
        printf("%d %d\n",k,sum-ans);
    }
    return 0;
}