1915 - 1351

C++解答

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
const int INF = 0x7f7f7f7f;
#define MIN(a,b) a<b?a:b
 
int n,match[N];
bool sx[N],sy[N];
int lx[N],ly[N],map[N][N];
int p[25][25],q[25][25];
bool path(int u)
{
    sx[u]=true;
    for(int v=0; v<n; v++)
        if(!sy[v]&&lx[u]+ly[v]==map[u][v])
        {
            sy[v]=true;
            if(match[v]==-1||path(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    return false;
}
int KM(bool truth)
{
    int i,j;
    if(!truth)
    {
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                map[i][j]=-map[i][j];
    }
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,-1,sizeof(match));
    for(int u=0; u<n; u++)
        while(1)
        {
            memset(sx,0,sizeof(sx));
            memset(sy,0,sizeof(sy));
            if(path(u))
                break;
            int dmin=INF;
            for(i=0; i<n; i++)
                if(sx[i])
                    for(j=0; j<n; j++)
                        if(!sy[j])
                            dmin=MIN(lx[i]+ly[j]-map[i][j],dmin);
            for(i=0; i<n; i++)
            {
                if(sx[i])
                    lx[i]-=dmin;
                if(sy[i])
                    ly[i]+=dmin;
            }
        }
    int sum=0;
    for(j=0; j<n; j++)
        sum+=map[match[j]][j];
    if(!truth)
    {
        sum=-sum;
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                map[i][j]=-map[i][j];
    }
    return sum;
}
 
void Map_Init(int n)
{
    int i,j;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            map[i][j]=-p[i][j]*q[j][i];
}
 
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i = 0; i <n; i++)
        for(j = 0; j <n; j++)
            scanf("%d",&p[i][j]);
    for(i = 0; i <n; i++)
        for(j =0 ; j <n; j++)
            scanf("%d",&q[i][j]);
    Map_Init(n);
    int cost=KM(false);
    printf("%d\n",-cost);
    return 0;
}