工作分配问题------基于dfs的回溯思想

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[22][22];
int vis[22];//标记工作
int pre[22];//预测前....人最小代价
int tot;
void dfs(int p,int q,int sum)
{
    if(p>q && sum < tot)
    {
        tot =sum;
        return;
    }

    if(sum + pre[q] - pre[p-1] < tot)
    {
        for(int j =1; j<=q; j++)
        {
            if(vis[j] == 0)
            {

                vis[j] =1;
                dfs(p+1,q,sum + a[p][j]);
                vis[j] = 0;
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
//输入同时对后面预测
    for(int i =1; i<=n; i++)
    {
        pre[i] =inf;
        for(int j = 1; j<=n; j++)
        {
            cin>>a[i][j];

            pre[i] = min(a[i][j],pre[i]);
        }
        pre[i] +=pre[i-1];
    }
//得到一个 初始结果
    tot =0;
    for(int i =1; i<=n; i++)
            tot += a[i][i];
//回溯法
    dfs(1,n,0);
    cout<<tot<<endl;


}