题解 P1559 【运动员最佳匹配问题】

SteinsGate0 · 2016-11-12 17:01:28 · 题解

我还以为是KM最佳匹配呢。。。

那样就很麻烦了----

因为不会。

不过既然n<20,就爆搜嘛，可行性剪枝就行

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,i,j,a[100][100],b[100][100],xx,aa[100];
int ans=0;
bool f[100],ff[100];
void dfs(int x,int v)
{
    int i;
if(x>n)
{
    if(v>ans)ans=v;
    return;
}
int vv=0;
for(i=x;i<=n;i++)
{vv+=aa[i];}
if(v+vv<ans)return;/////可行性剪枝哦
for(i=1;i<=n;i++)
{
    if(ff[i]==false)
    {
        ff[i]=true;
        dfs(x+1,v+a[x][i]*b[i][x]);
        ff[i]=false;
            }
    }
}
    int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        scanf("%d",&a[i][j]);
            }
         for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        scanf("%d",&b[i][j]);
            }
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        aa[i]=max(a[i][j]*b[j][i],aa[i]);
    }
    dfs(1,0);
    cout<<ans;
}