1018 Public Bike Management 结题记录(dfs剪枝)

这篇具有很好参考价值的文章主要介绍了1018 Public Bike Management 结题记录(dfs剪枝)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人觉得直接放入代码是最管用的。
其他方法类似,题意请参考其他博主。文章来源地址https://www.toymoban.com/news/detail-681921.html

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;

int maxn = 2000000000;
int c, n, ed, s[N], m, minlen, needn, backn, pre[N];
bool flag, book[N];
vector<pair<int, int > > e[N];

inline void dfs(int u, int points, int maxneed, int stores, int len)
{
    if (len > minlen) return ;
    int nd = points * c / 2 - stores;
    
    maxneed = max(maxneed, max(0, nd));

    if (u == ed) {
        int tneedn, tbackn;
        if (nd <= 0) {
            // dont need
            tneedn = maxneed; tbackn = -nd + maxneed;
        } else {
            // need;
            tneedn = max(maxneed, nd); tbackn = 0;
        }
        if (len == minlen) {
            if (needn > tneedn || (needn == tneedn && backn > tbackn)) {
                needn = tneedn; backn = tbackn;
            } 

        } else if (minlen > len) {
            minlen = len; needn = tneedn; backn = tbackn;
        }
        return ;
    }

    for (int i = 0; i < e[u].size(); i++) {
        int v = e[u][i].first, w = e[u][i].second;
        if (book[v]) continue;
        book[v] = true;
        dfs(v, points + 1, maxneed, stores + s[v], len + w);
        book[v] = false;
    }
}

inline void dfs2(int u, int points, int maxneed, int stores, int len)
{
    if (flag) return ;
    if (len > minlen) return ;

    int nd = points * c / 2 - stores;
    maxneed = max(maxneed, max(0, nd));

    if (u == ed) {
        int tneedn, tbackn;
        if (nd <= 0) {
            // dont need
            tneedn = maxneed; tbackn = -nd + maxneed;
        } else {
            // need;
            tneedn = max(maxneed, nd); tbackn = 0;
        }
        if (len == minlen) {
            if (tneedn == needn && tbackn == backn) {
                // puts("test 1");
                flag = true;
            }
        } 
        return ;
    }

    for (int i = 0; i < e[u].size(); i++) {
        int v = e[u][i].first, w = e[u][i].second;
        if (book[v]) continue;
        book[v] = true;
        pre[v] = u;
        dfs2(v, points + 1, maxneed, stores + s[v], len + w);
        if (flag) return ;
        book[v] = false;
    }
}

signed main()
{
    scanf("%d%d%d%d", &c, &n, &ed, &m);

    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    minlen = maxn, needn = maxn, backn = maxn;
    book[0] = true;
    dfs(0, 0, 0, 0, 0);

    // printf("%d %d %d\n", minlen, needn, backn);

    memset(book, 0, sizeof book);
    book[0] = true;
    dfs2(0, 0, 0, 0, 0);

    vector<int > res;
    while (ed != 0) {
        res.push_back(ed); ed = pre[ed];
    }
    
    printf("%d %d", needn, 0);

    for (int i = res.size() - 1; i >= 0; i--) {
        printf("->%d", res[i]);
    }

    printf(" %d\n", backn);

    return 0;
}

到了这里,关于1018 Public Bike Management 结题记录(dfs剪枝)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • DFS:深搜+回溯+剪枝解决组合问题

                                                   创作不易,感谢支持!!! . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 该题和前面是类似的,但是用回溯算法,会超

    2024年04月12日
    浏览(39)
  • 组合(力扣)dfs + 回溯 + 剪枝 JAVA

    给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2: 输入:n = 1, k = 1 输出:[[1]] 提示: 1 = n = 20 1 = k = n 解题思路: 1.每个元素有选与不选两种情况,

    2024年02月16日
    浏览(53)
  • DFS:深搜+回溯+剪枝解决排列、子集问题

                                        创作不易,感谢三连支持!!  . - 力扣(LeetCode) . - 力扣(LeetCode)  方案1:不合法就continue 方案2:合法才能进循环 . - 力扣(LeetCode) . - 力扣(LeetCode)  策略1:决策树以选不选作为参考,结果为叶子节点 策略2:决策树以选几个

    2024年04月16日
    浏览(66)
  • DFS:深搜+回溯+剪枝解决矩阵搜索问题

                                                   创作不易,感谢三连!!  . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 1、矩阵搜索问题经常要用到向量,也就是我们可以通过dx和dy来帮助我们定义方向

    2024年04月17日
    浏览(41)
  • Acwing166 数独题解 - DFS剪枝优化

    166. 数独 - AcWing题库 数独 是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。 请编写一个程序填写数独。 搜索+剪枝(优化搜索顺序、位运算) 优化搜索顺序:很明显,我们肯定是从当前能填合法数字

    2024年03月10日
    浏览(51)
  • 【Acwing187】导弹防御系统(LIS+剪枝+贪心+dfs+迭代加深)

    1.最长上升子序列(lis)的算法思想和算法模板 2.acwing1010拦截导弹(lis+贪心)题解   本题题解,需要知道这种贪心算法 3.简单了解dfs暴力搜索、剪枝、搜索树等概念 dfs求最小步数有两种方法:记一个全局最小值,迭代加深 bfs的缺点:空间太大、不好剪枝 此处采用dfs的迭代

    2024年02月07日
    浏览(36)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1753 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 游泳池可以等分为n行n列的小区域,每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。 而小明对温度十分

    2024年02月10日
    浏览(38)
  • 【算法心得】正确估计dfs时间复杂度;剪枝优化不怕重构

    https://leetcode.cn/problems/verbal-arithmetic-puzzle/ 这题看到题,“表达式中使用的不同字符数最大为 10”,就觉得dfs就完事了,最多不过10!,10!才1e6,1e7这样。如果字符再少点,6! 7! 8!的,那简直就是嗖的一下就跑完了 结果TLE了 比方说,有7个字符,不是想象中的 7!,而是 10*9*...*4 ,

    2024年02月12日
    浏览(43)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(50)
  • 每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝

    目录 力扣814. 二叉树剪枝 解析代码 814. 二叉树剪枝 难度 中等 给你二叉树的根结点  root  ,此外树的每个结点的值要么是  0  ,要么是  1  。 返回移除了所有不包含  1  的子树的原二叉树。 节点  node  的子树为  node  本身加上所有  node  的后代。 示例 1: 示例 2: 示

    2024年02月22日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包