P2457题解

· · 题解

基本思路：KM 算法求最优匹配

如果你不会 KM 算法请点这里

先来定义一些数组方便下面表达：

int n,m,mp[N][N];//mp存放输入的矩阵
int sum[N];//sum存放每一种货物重量的总和 
int va[N],vb[N]//va，vb标记每一次dfs左右参与的点
int w[N][N];//w存放把i其余所有货物搬到仓库j的代价 
int la[N],lb[N]//la，lb分别为左右标杆
int mi[N];//mi为右部点匹配的点
int vis[N];//vis标记当前dfs每一个点最少下降多少可以有其他的选择

题目给出的输入第 i 行是仓库 i 所存放的第 j 种货物的重量，如果要用仓库 i 来存放货物 j，那就需要把其他仓库里的货物 j 给搬到仓库 i，代价为 sum_{j}-mp[i][j]，所以输入 mp 数组的同时把 sum 数组给处理出来，然后把 w 数组处理出来，左部点为仓库编号，右部点为货物种类编号，跑 KM 算法就好啦。

这题让着求最小代价，和一般的不太一样怎么办？

只要在处理 w 数组的时候存的边权一取反，跑 KM 的时候不久就可以找最优匹配了吗，最后输出别忘了取反。

code：

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define N 510
using namespace std;
int n,m,mp[N][N],sum[N];//mp存放输入的矩阵，sum存放每一种货物重量的总和 
int va[N],vb[N],w[N][N];//va，vb标记每一次dfs左右参与的点，w存放把i其余所有货物搬到仓库j的代价 
int la[N],lb[N],mi[N],vis[N];//la，lb分别为左右标杆，mi为右部点匹配的点，
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
} 
inline int dfs(int x)//匈牙利算法 
{
    va[x]=1;//标记参与本次dfs 
    for(int i=1;i<=n;i++)//枚举每一个右部的点 
      if(w[x][i])//如果当前两点之间存在边 
        if(!vb[i])//vb没有标记已经搜过了 
        {
            if(la[x]+lb[i]==w[x][i])//如果当前左右标杆加起来等于边权 
            {
                vb[i]=1;//标记可以 
                if(!mi[i]||dfs(mi[i]))//如果当前右部点没有与之相匹配的点或者与之相匹配的点可以与其他点匹配 
                {
                    mi[i]=x;//当前左部点与右部点匹配 
                    return 1;//返回匹配成功 
                }
            }
        else vis[i]=min(vis[i],la[x]+lb[i]-w[x][i]);//如果不等于边权，求出下降最小可以有其他解的值 
        }
    return 0;//返回匹配失败 
}
int KM()//KM算法板子 
{
    for(int i=1;i<=n;i++)
    {
        la[i]=-INF;
        lb[i]=0;
        for(int j=1;j<=n;j++)
          la[i]=max(la[i],w[i][j]);//给左部标杆赋初值 
    }
    for(int i=1;i<=n;i++)//匹配每一个左部点 
    {
        while(1)
        {
            memset(va,0,sizeof(va));//每次都要清空va，vb 
            memset(vb,0,sizeof(vb));
            for(int j=1;j<=n;j++)
              vis[j]=INF;//赋初值，vis表示每一个点最少下降多少可以有另一种选择 
            if(dfs(i))break;//如果当前点匹配成功直接退出 
            int d=INF;//赋初值 
            for(int j=1;j<=n;j++)
              d=min(d,vis[j]);//取每一个vis的最小值 
            for(int j=1;j<=n;j++)
            {
                if(va[j])la[j]-=d;//左部点减d 
                if(vb[j])lb[j]+=d;//右部点加d 
            }
        }
    }
    int ans=0;//ans表示答案 
    for(int i=1;i<=n;i++)//枚举每一个右部点 
      ans+=w[mi[i]][i];//累加所选的边权 
    return ans;//返回答案 
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;
            x=read();
            mp[i][j]=x;//存图 
            sum[j]+=x;//累加一种货物的重量总和 
        }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      w[i][j]=-(sum[i]-mp[j][i]);//转换一下求出要把所有货物放到最此仓库的代价，取相反数求最大边权匹配 
    printf("%d",-KM());//输出的时候别忘了取反 
    return 0;
}//by wwwaax