洛谷 2210 [USACO] Haywire dfs+剪枝

54 阅读 0 评论 36 点赞

我是靠谱客的博主正直帆布鞋，最近开发中收集的这篇文章主要介绍洛谷 2210 [USACO] Haywire dfs+剪枝，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

https://www.luogu.org/problem/show?pid=2210

这是个好题；

虽然
暴力=65分
暴力+卡时=92分……

思路：
显然，我们可以用全排列+统计来解决这个问题；
但是：n！* n * 3的复杂度难以承受的；
12！ * 12 * 3=17244057600；

我们考虑剪枝与优化；

可以转化状态；
pos[i]：第i头奶牛的位置;
这样，我们可以边搜，边统计答案，
12！*3=1437004800

常数太大，还是不够优；

考虑剪枝:
因为本题不存在不合法的情况；
所以只能加最优化剪枝；

我们可以应用A*的思想；

x：第x位；
nowtot：当前总距离；
links：已经访问的所有奶牛中，有多少路线没有找到，(即某奶牛的朋友还没有找到)；
remain：已经访问的所有奶牛中，没有找到的路线的长度总和，（是当前，并不是所有，当前就已经够了）；

因为每条路线至少是1，所以我们假定所有没找到的路线开始都为1；

每次，remain+links，即当前位置，还没有找到的所有路线都+1（显然）;
因此remain是我们的方案的下限,即最小的估值（不可能更小了）；

其实，这只是个“随机”值，但这个随机值不会让答案错误；
所以说正确估价尤其重要；

if(remain+nowtot >= ans) return;
很高效的剪枝；
加上轻松AC；

总结：
dfs的优化：
1. 剪枝，最优化剪枝；可以预处理出一些极限值（最大，最小，例：生日蛋糕，本题等）；可行性剪枝（虫食算、迷宫等）;
一般找极限值的剪枝要多一些；
2. 状态的优化：减少时间复杂度(靶形数独等),减少编程复杂度（虫食算，斗地主等）;
3. 少开函数，尽量边dfs边计算；可以先写个函数，逐步加入dfs中；（斗地主等）
4. 出发点的优化（引水入城等）；
5. 预处理一些值，避免dfs时重复计算(吃奶酪等);
6. 记忆化搜索(滑雪等);
7. 限制深度的dfs（埃及分数等） ~~这个……~~
8. dfs运用A*的思想(斗地主，本题等);
9. 卡时

一言以蔽之：在不影响答案的情况下，尽量少搜无用结点，多做”有意义的事情”；

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int MAXN=21;
int fr[MAXN][5],a[MAXN],pos[MAXN];
int n,ans=2134212,cnt;
bool vis[MAXN];

void dfs(int x,int nowtot,int links,int remain)
{

    if(x==n+1)
        ans=min(ans,nowtot);

    if(remain+nowtot >= ans) return;//最优化剪枝


    for(register int i=1;i<=n;i++)
    {
        if(!pos[i])
        {
            int new_link=3,sum=0;//每个奶牛开始有三个朋友;
            pos[i]=x;//第i个奶牛放在x上; 
            for(int j=1;j<=3;j++)
            {
                if(pos[fr[i][j]]!=0)
                {
                    sum+=abs(x-pos[fr[i][j]]);//发现这条路线已经确定;
                    new_link-=2;//以前的friend对当前奶牛的路线-1,当前奶牛同样-1,总的减2； 
                }
            }
            dfs(x+1,nowtot+sum,links+new_link,remain+(links+new_link)-sum);
            pos[i]=0;
        }
    }
    return;
}

void solve()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=3;j++)
            scanf("%d",&fr[i][j]);

    dfs(1,0,0,0);

    cout<<ans;
}

int main()
{
    solve();
    return 0;
}