AcWing 4957. 简单的dfs（详细的注释）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4957. 简单的dfs（详细的注释）原题链接简单

作者：

_Dijkstra , 2023-04-11 22:19:13 , 所有人可见 , 阅读 7624

94

21

暴力模拟

数据量很小，考虑所有的排列情况然后判定是否可以全部降落即可

使用dfs剪枝可以提高效率

#include<iostream>
#include<cstring>

using namespace std;

int t,n,a[15][3];
bool st[15],flag;//st记录是否已经降落，flag标记是否降落完成

void dfs(int k,int last)//k表示已经降落的飞机数量，last表示上一架飞机降落完成的时间
{
    if(k>=n)//已经全部降落
    {
        puts("YES");
        flag=true;
    }
    if(flag) return;//已经完成就不再搜索

    for(int i=1;i<=n;i++)//枚举每一种情况
    {
        if(!st[i])//还没降落
        {
            if(a[i][1]<last) return;//如果最迟降落时间已经过去就不满足，剪掉
            st[i]=true;
            if(last<a[i][0]) dfs(k+1,a[i][0]+a[i][2]);//降落时间小于当前飞机的最早降落时间就等到了再降落
            else dfs(k+1,last+a[i][2]);//否则上一架完成这架立马降落
            st[i]=false;//还原现场
        }
    }
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(st,0,sizeof st);//设置为都未降落
        flag=false;//还没完成

        for(int i=1;i<=n;i++)
        {
            cin>>a[i][0]>>a[i][1]>>a[i][2];
            a[i][1]+=a[i][0];//到达时间加上盘旋时间==最迟降落时间
        }

        dfs(0,0);
        if(!flag) puts("NO");//所有的情况都不满足
    }

    return 0;
}

29 评论

所念皆星河1 2023-04-14 21:24

这个dfs写的真漂亮

炽热小老弟 2023-04-15 10:26

抓住了哈哈哈

Hzhzl12Td 2023-04-13 20:21

if (u == n)
{
path = true;
cout << “YES” << endl;
return;
}
// if (path) return;
请问这里的return为什么不能直接写在if语句中，不知道为什么555

_Dijkstra 2023-04-13 21:07

不是很理解问的问题ovo
if (u == n)
{
path = true;
cout << “YES” << endl;
return;
}
if (path) return;
这样应该也是可以的吧

Hzhzl12Td 2023-04-13 21:09 回复了 _Dijkstra 的评论

我没有写最后那个if (path) return;我只写了
if (u == n)
{
path = true;
cout << “YES” << endl;
return;
}

_Dijkstra 2023-04-13 21:15 回复了 Hzhzl12Td 的评论

if(path) return;
这样写是因为，确定了降落了，就将其他的递归程序全部返回，不再执行，提高效率
只在里面写return只会终止当前的函数

Hzhzl12Td 2023-04-13 21:27 回复了 _Dijkstra 的评论

不太理解这个当前和其他递归程序是什么，当u==n最后一步了，在里面输出完yes直接return不也可以退出递归程序，你的意思难道是其实最后一步对于每一组飞机u==n有很多组，在外面写可以直接退出主函数中的bfs吗|ω・）

_Dijkstra 2023-04-13 21:44 回复了 Hzhzl12Td 的评论

因为你return是返回到上一层，如果没有这个flag的话，这个递归程序不知道他已经完成了降落这个任务，他会从上一层继续往下搜。
加了这个flag，他要往下搜的时候就会知道，降落完成了，就不搜了，return掉

Hzhzl12Td 2023-04-13 22:41 回复了 _Dijkstra 的评论

好吧谢谢你了

心态要稳呐 7个月前回复了 _Dijkstra 的评论

我试了试，确实是这样的，不过我想不通的是，这是为什么呢，为什么在里边写return就会返回上一步的递归程序，在外边写就终止程序了？

柴柴_2 7个月前回复了心态要稳呐的评论

都是返回上一个递归程序，但是AC不了，因为爆搜到其他方案符合的时候有这个flag就return掉就直接结束并没有执行输出yes，而写在里面会输出yes，你便看到输出非常多的yes，那便是爆搜其他符合条件的方案时输出的yes

一一呀 7个月前

#include <bits/stdc++.h>
using namespace std;

int T, n;
bool st[15];
struct Plane
{
    int t, d, l;
} a[15];

bool dfs(int u, int last) //u表示已经降落的飞机数量，last表示上一架飞机降落完成的时间
{
    if (u == n) return true;
    for (int i = 0; i < n; i++)
    {
        int t = a[i].t, d = a[i].d, l = a[i].l;
        if (!st[i] && t + d >= last)
        {
            st[i] = true;
            if (dfs(u + 1, max(last, t) + l)) return true;
            st[i] = false; //恢复现场
        }
    }
    return false;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int t, d, l;
            scanf("%d%d%d", &t, &d, &l);
            a[i] = {t, d, l};
        }
        memset(st, 0, sizeof st);
        if (dfs(0, 0)) puts("YES"); //从已经降落的飞机数量为0 降落时间为0的点开始搜索
        else puts("NO");
    }
    return 0;
}