[P1171]售货员的难题-玄学

· · 题解

DFS深度优先搜索 + sort排序优化 + 玄学

先对所有线段进行排序，然后在dfs的时候优先选择价值小的东西。记得在dfs的时候剪枝。 有两处剪枝

第一处是当答案已经大于最小的时候，直接return

第二处是在剩下的物品(假设每个物品价值为最小即为1)都取1的时候，如果现在答案+剩下物品和已经大于ans了，那就return了

#include <bits/stdc++.h>
#pragma GCC target("f16c")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
using namespace std;
const int maxn = 25;
const int inf = 0x3f3f3f3f;
int n;
int G[maxn][maxn];
bool vis[maxn];
int ans = inf;
struct node{
    int w;int to;
}GG[maxn][maxn];
int org[maxn];
int minL = inf;
void dfs(int u,int cnt,int sum){
    if(cnt == n){
        ans = min(ans,sum+org[u]);
        return;
    }
    if(sum+(n-cnt)+1 > ans) return;
    if(sum > ans){
        return;
    }

    //cout << sum << endl;


    /*
    for(int i=1;i<=n;i++){
        if(!vis[i] && i != u){
            dfs(i,cnt+1,sum+G[u][i]);
        }
    }
    */
    for(int i=2;i<=n;i++){
        if(!vis[GG[u][i].to]){
            int v = sum + GG[u][i].w;
            if(v > ans)return;
            if(v + n - cnt + minL > ans)return;
            vis[GG[u][i].to] = true;
            dfs(GG[u][i].to,cnt+1,sum + GG[u][i].w);
            vis[GG[u][i].to] = false;
        }
    }

}
bool mycmp(node a,node b){
    return a.w < b.w;
}
int main(){
    //freopen("1171.txt","r",stdin);
    scanf("%d",&n);
    int w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&w);
            GG[i][j].w = w;
            GG[i][j].to = j;
            G[i][j] = w;
        }
        org[i] = GG[i][1].w;
        if(i != 1){
            minL = min(minL,org[i]);
        }
        sort(GG[i]+1,GG[i]+1+n,mycmp);
    }
    memset(vis,0,sizeof vis);
    vis[1] = 1;
    dfs(1,1,0);
    cout << ans;
    return 0;
}