`
249326109
  • 浏览: 56060 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

pat 1018. Public Bike Management (30)

 
阅读更多

链接:http://pat.zju.edu.cn/contests/pat-a-practise/1018

 

题意(转biaobiaoqi):以杭州的公用自行车站点管理为背景。每个站点是一个节点,每个节点上最多停放 Cmax 辆自行车,Cmax/2 为节点的最佳状态。不同节点间距离不同,整个构成了一张带权无向图。要求从起始点(公用自行车管理中心)出发,去目的地维护目的地节点的车辆状态,如果车辆低于 Cmax/2,则给它添加车辆到 Cmax/2 辆,如果多于 Cmax/2,则去除掉几辆车。同时,在去往目的地的过程中,也需要调整所有沿途站点的车辆(这里题目没有交代清楚,实际测试是只能在去往目的地的途中调整,回来的途上不可调整)。求到给定目的地的最短路径,如果有多条最短路径,则按照 1.从管理中心送出的车辆越少越好;2.拿回到管理中心的车越少越好的优先级找到结果。

 

 

分析:首先利用dijkstra算法求出最短路径的长度,然后dfs求出所有的最短路径,然后在其中寻找题目要求的最优的路径。

 

#include<stdio.h>
#include<vector>

using namespace std;

#define Inf 100000000
int c, n, sp, m;
int bikeNum[505];
int mat[505][505];
int found[505];
int d[505];
int p[505];

int visited[505];
vector<vector<int> > shortestPaths;

int getMinIdx() {
	int i;
	int minDis = Inf;
	int minIdx = -1;
	for (i = 0; i <= n; i++) {
		if (!found[i] && d[i] < minDis) {
			minDis = d[i];
			minIdx = i;
		}
	}
	return minIdx;
}

void dfs(int v, int dis, int num, vector<int>& vec) {
	vec.push_back(v);
	if (dis > d[sp]) {
		vec.pop_back();
		return;
	}

	if (v == sp && dis == d[sp]) {
		shortestPaths.push_back(vec);
		vec.pop_back();
		return;
	}
	visited[v] = 1;
	int i;
	for (i = 0; i <= n; i++) {
		if (!visited[i] && mat[v][i])
			dfs(i, dis + mat[v][i], num + bikeNum[v] - c / 2, vec);
	}
	visited[v] = 0;
	vec.pop_back();
	return;
}

int main() {
//	freopen("in.txt", "r", stdin);
	scanf("%d%d%d%d", &c, &n, &sp, &m);
	int i;
	for (i = 1; i <= n; i++)
		scanf("%d", &bikeNum[i]);
	int from, to, dis;
	for (i = 0; i < m; i++) {
		scanf("%d%d%d", &from, &to, &dis);
		mat[from][to] = dis;
		mat[to][from] = dis;
	}

	d[0] = 0;
	for (i = 1; i <= n; i++)
		d[i] = Inf;
	for (i = 0; i <= n; i++)
		p[i] = -1;
	int idx;
	do {
		idx = getMinIdx();
		found[idx] = 1;
		int i;
		for (i = 0; i <= n; i++) {
			if (mat[idx][i] && !found[i])
				if (d[i] > d[idx] + mat[idx][i]) {
					d[i] = d[idx] + mat[idx][i];
					p[i] = idx;
				}

		}

	} while (idx != sp);

	vector<int> path;
	dfs(0, 0, 0, path);

	int j;
	int minSendBikeNum = Inf;
	int minBikeBackNum = Inf;

	int sendBikeNum[10000];
	int bikeBackNum[10000];

	for (i = 0; i < shortestPaths.size(); i++) {
		int sum = 0;
		int minNum = Inf;
		int tmpSum = 0;
		for (j = 0; j < shortestPaths[i].size(); j++) {
			sum += bikeNum[shortestPaths[i][j]];
			if (j) {
				tmpSum += bikeNum[shortestPaths[i][j]] - c / 2;
				if (tmpSum < minNum) {
					minNum = tmpSum;
				}
			}
		}
//		printf("minNum:%d\n", minNum);

		int tmp = (shortestPaths[i].size() - 1) * c / 2 - sum;
		if (tmp >= 0) {
			sendBikeNum[i] = tmp;
			bikeBackNum[i] = 0;
		} else {
			sendBikeNum[i] = 0;
			bikeBackNum[i] = -tmp;
		}
		if (minNum < 0) {
			sendBikeNum[i] = -minNum;
			bikeBackNum[i] = -tmp-minNum;
		}

	}

	for (i = 0; i < shortestPaths.size(); i++) {
		if (sendBikeNum[i] < minSendBikeNum) {
			minSendBikeNum = sendBikeNum[i];
		}
	}
	int resultIdx = -1;
	for (i = 0; i < shortestPaths.size(); i++) {
		if (sendBikeNum[i] == minSendBikeNum) {
			if (bikeBackNum[i] < minBikeBackNum) {
				minBikeBackNum = bikeBackNum[i];
				resultIdx = i;
			}

		}

	}
	printf("%d ", sendBikeNum[resultIdx]);

	for (i = 0; i < shortestPaths[resultIdx].size(); i++) {
		if (i != 0)
			printf("->");
		printf("%d", shortestPaths[resultIdx][i]);
	}
	printf(" %d\n", bikeBackNum[resultIdx]);

	return 0;
}

 

 

分享到:
评论

相关推荐

    CAD填充图案(三百多种)-.pat文件

    CAD填充图案(三百多种)-.pat文件 部分如下(篇幅有限) 2x12木地板.pat 45度人字形砖面(1).pat 8x8无缝砖.pat Z形砖.pat 丁字砖面1.pat 丁字砖面2.pat 三联蜂窝.pat 三角形拼铺.pat 不能通行的沼泽地.pat 乱沙.pat...

    pat1.cpp

    pat1.cpp

    pat1.rar_in

    标题“pat1.rar_in”可能指的是一个包含图像处理补丁的压缩文件,而“in”标签可能是对内容的简要分类或关键词。压缩文件中的唯一子文件“pat1.m”很可能是一个MATLAB脚本,因为.m文件是MATLAB的源代码文件格式。...

    Neural Networks and Deep Learni - Pat Nakamoto.azw3

    Neural Networks and Deep Learni - Pat Nakamoto.azw3

    数据结构 算法 ACM PAT .......zip

    算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...

    PAT答案_1001至1049

    5. **pat1018.cpp**:可能是线性数据结构(数组、链表)的操作,如插入、删除、查找等,也可能涉及到栈或队列的应用。 6. **pat1021.cpp**:这题可能与递归或回溯法有关,常见于解决组合问题、迷宫问题、八皇后问题...

    dcu2pat,make Delphi .dcu to .pat!!

    dcu2pat.exe I:\delphi.trash\2007\lib\*.dcu wc -l .pat 26959 .pat \ida\flair\bin\sigmake.exe .pat d2007.sig : modules/leaves: 11149849/26655, COLLISIONS: 19389 After resolving of collisions (see ...

    Paragon Alignment Tool_PAT.3.0.13045

    Paragon Alignment Tool_PAT.3.0.13045 内置激活码、中文版使用说明(PDF文档,工具安装后是英文界面,可参照中文版使用说明); 工具可用于SSD固态硬盘、机械硬盘、U盘、SD卡/TF卡等移动存储设备4K对齐,支持无损...

    PAT3.Setup.3.5.1.64.msi

    是由新加坡国立大学开发的一款形式化建模与验证工具集,支持进程代数、实时进程代数、时间自动机等多种建模语言...PAT工具的人机交互界面友好,支持多种验证方法,包括精化验证、死锁验证、可达性验证、LTL性质验证等。

    acwing, leetcode, kickstart, 算法模板, PAT 等等.zip

    标题中的“acwing, leetcode, kickstart, 算法模板, PAT 等等.zip”表明这是一个包含多个算法训练平台资源的压缩文件。这些平台都是程序员提升算法能力、准备编程竞赛的重要工具。让我们逐一深入探讨它们以及可能...

    CAD填充图案 acadiso.pat

    把acadiso.pat放到c:\Documents and Settings\当前用户名\Application Data\Autodesk\AUTOCAD 2009\R17.2\CHS\SUPPORT 文件下 适合各中版本的CAD

    DSM_DS918+_24922.pat

    黑群晖最经典的版本 DSM_DS918+_24922.pat

    考场上面的注意事项(PAT).zip

    适合在打基础的同学可以比较深入提前了解比较真实的做题情况,减少焦虑(无解压密码,解压后获得TXT文件)

    PAT 1009. 说反话 (20)

    1009. 说反话 (20) 给定一句英语,要求你编写程序,将句中所有单词的顺序颠倒输出。 输入格式:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由...

    TS 包解析包括ts头 pes pat pmt .

    根据给定的信息,本文将详细解释TS(Transport Stream)包解析中的关键概念,包括TS头、PAT(Program Association Table)、PMT(Program Map Table)以及PES(Packetized Elementary Stream)。这些是MPEG-2传输流...

    MIS管理系统使用说明-客户doc - PAT项目.doc

    MIS(Management Information System,管理信息系统)是现代企业信息化管理的重要工具,它整合了数据处理、业务流程与决策支持等功能,为企业提供高效的信息服务。PAT项目中的MIS管理系统,特别针对客户管理进行了...

    patb工程文件说明

    patb工程文件的说明文档,对patb工程文件的说明。adj、image、ori、cont。

    patb.rar_enjoy3b8_newton_newton-raphson_数学计算_非线性有限元

    标题 "patb.rar_enjoy3b8_newton_newton-raphson_数学计算_非线性有限元" 涉及的主题是使用Newton-Raphson方法解决一维非线性问题,具体应用在有限元分析中。Newton-Raphson方法是一种强大的数值迭代技术,常用于...

    配置PAT.docx

    ### 配置PAT知识点详解 #### 一、PAT(Port Address Translation)概念解析 PAT(端口地址转换),是NAT(Network Address Translation)的一种特殊形式,主要用于将一个内部网络中的多个私有IP地址映射到一个或...

    安全认证 《2020网络安全人才发展白皮书》 - pat考试.zip

    安全认证 《2020网络安全人才发展白皮书》 - pat考试 安全管理 安全管理 WEB应用防火墙 金融安全 无线安全

Global site tag (gtag.js) - Google Analytics