1018. Public Bike Management 解析

2023-11-26 16:32

本文主要是介绍1018. Public Bike Management 解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

单用Dijstra算法比较难维护。用Dijstra+DFS能简化不少。

看到有小伙伴例7有问题,可以看下是不是Dijstra的算法在计算路径的时候出问题没。我的就是下标u和i弄混了。查了好久。。。。。


#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <stack>using namespace std;struct Node {int length;int Num;
};struct Grap {int bIkeNum;vector <Node> link;
};void Dijkstra(Grap * g, int * dis ,vector<int> * pre ,int N,bool * isvisit ) {dis[0] = 0;for (int i = 0; i < N; i++) {int u = -1, Min = INT_MAX;for (int j = 0; j < N; j++) { //找Dis最小值if (!isvisit[j] && dis[j] < Min) {u = j;Min = dis[j];}}if (u == -1) return;isvisit[u] = true;		for (int j = 0; j < g[u].link.size(); j++) {int v = g[u].link[j].Num;if (!isvisit[v]) {if (dis[u] + g[u].link[j].length < dis[v]) {//u是中间结点pre[v].clear();pre[v].push_back(u);dis[v] = dis[u] + g[u].link[j].length;}else if (dis[u] + g[i].link[j].length == dis[v]) {pre[v].push_back(u);}}}}
}void DFS(vector <int> * pre, vector <int> & patch, vector <int> & tempatch, Grap * g, int & BikeNeed, int & BikeReturn, int v, int Cmax) {//cout << " v = " << v << endl;int perfect = Cmax / 2;if (v == 0) {tempatch.push_back(v);int bn = 0, br = 0;//计算大小//cout << "size: " << tempatch.size() << endl;for (int i = tempatch.size() - 1; i >= 0; i--) {int b = g[tempatch[i]].bIkeNum;if (b > perfect) {//大于perfect需要带走br += b - perfect;}else if (b < perfect){ //补齐br -= (perfect - b);//			cout << "br : " << br <<  endl;if (br < 0) {//不够补齐 要从中心调bn += (-br);br = 0;}}}//判断if (bn < BikeNeed) {BikeNeed = bn;BikeReturn = br;patch = tempatch;}else if (bn == BikeNeed && br < BikeReturn) {BikeNeed = bn;BikeReturn = br;patch = tempatch;}tempatch.pop_back();return;}tempatch.push_back(v);for (int i = 0; i < pre[v].size(); i++) {DFS(pre, patch, tempatch, g, BikeNeed, BikeReturn, pre[v][i], Cmax);}tempatch.pop_back();}int main() {int Cmax, N, SP, M;//Cmax最大容量,N站总数,SP问题站编号,M道路总数cin >> Cmax >> N >> SP >> M;Grap * g = new Grap[N + 1];stack <int> s;for (int i = 1; i <= N; i++) {cin >> g[i].bIkeNum;}g[0].bIkeNum = Cmax / 2;Node tempNode;int tempHead, tempTail;for (int i = 0; i < M; i++) {cin >> tempHead >> tempTail >> tempNode.length;tempNode.Num = tempTail;g[tempHead].link.push_back(tempNode);//cout << tempHead << " " << tempNode.Num << " " << tempNode.length << endl;tempNode.Num = tempHead;g[tempTail].link.push_back(tempNode);//cout << tempTail << " " << tempNode.Num << " " << tempNode.length << endl;}//	int MinLegnth = INT_MAX;bool * isVisit = new bool[N + 1];int * dis = new int[N + 1];vector <int> * pre = new vector<int>[N + 1];for (int i = 0; i <= N; i++) {dis[i] = INT_MAX;isVisit[i] = false;}Dijkstra(g, dis, pre, N + 1, isVisit);int BikeNeed = INT_MAX, BikeReturn = INT_MAX;vector <int> patch, tempatch;DFS(pre, patch, tempatch, g, BikeNeed, BikeReturn, SP, Cmax);cout << BikeNeed << " ";for (int i = patch.size() - 1; i > 0; i--) {cout << patch[i] << "->";}cout << patch[0] << " ";cout << BikeReturn << endl;system("pause");return 0;
}


这篇关于1018. Public Bike Management 解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/426018

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

OWASP十大安全漏洞解析

OWASP(开放式Web应用程序安全项目)发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南,它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析: 1. 注入漏洞(Injection) 描述:攻击者通过在应用程序的输入数据中插入恶意代码,从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响:可能导致数据泄

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动

Spring 源码解读:自定义实现Bean定义的注册与解析

引言 在Spring框架中,Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义,Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制,帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry,以全面掌握Bean注册和解析的核心原理。

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

多线程解析报表

假如有这样一个需求,当我们需要解析一个Excel里多个sheet的数据时,可以考虑使用多线程,每个线程解析一个sheet里的数据,等到所有的sheet都解析完之后,程序需要提示解析完成。 Way1 join import java.time.LocalTime;public class Main {public static void main(String[] args) thro

ZooKeeper 中的 Curator 框架解析

Apache ZooKeeper 是一个为分布式应用提供一致性服务的软件。它提供了诸如配置管理、分布式同步、组服务等功能。在使用 ZooKeeper 时,Curator 是一个非常流行的客户端库,它简化了 ZooKeeper 的使用,提供了高级的抽象和丰富的工具。本文将详细介绍 Curator 框架,包括它的设计哲学、核心组件以及如何使用 Curator 来简化 ZooKeeper 的操作。 1

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can

图解TCP三次握手|深度解析|为什么是三次

写在前面 这篇文章我们来讲解析 TCP三次握手。 TCP 报文段 传输控制块TCB:存储了每一个连接中的一些重要信息。比如TCP连接表,指向发送和接收缓冲的指针,指向重传队列的指针,当前的发送和接收序列等等。 我们再来看一下TCP报文段的组成结构 TCP 三次握手 过程 假设有一台客户端,B有一台服务器。最初两端的TCP进程都是处于CLOSED关闭状态,客户端A打开链接,服务器端