PAT（甲级）2021年春季考试 7-4 Recycling of Shared Bicycles
解题思路：
先用Floyd算法求出全员最短路径矩阵。
然后使用DFS进行遍历，遍历的原则是就近贪心，对于每一个点先遍历离他最近的未访问点。
记录访问点的个数，同时用数组存放已访问点，如果访问点的个数不等于输入点数+1(加一是因为访问点把起点也算上了而输入时没有)，说明不连通。
注：以下代码仅仅通过了给出的2个测试用例。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int maxn = 210;
const int inf = 1000000000;//即10^9 int Adj[maxn][maxn]; int vNum,eNum;bool vis[maxn] = {0};
int visNum = 0;int totalDis = 0;
int path[maxn] = {0};void DFS(int u){vis[u] = 1;path[visNum++] = u;int MIN = inf,v = -1;for(int i=0;i<=vNum;i++){ if(Adj[u][i]<MIN&&vis[i]==false){v = i;MIN = Adj[u][i];}}if(v==-1)return;totalDis += Adj[u][v];DFS(v);
}void Floyd(){for(int k=0;k<=vNum;k++){for(int i=0;i<=vNum;i++){for(int j=0;j<=vNum;j++){if(Adj[i][k]!=inf&&Adj[k][j]!=inf&&Adj[i][j]>Adj[i][k]+Adj[k][j]){Adj[i][j] = Adj[i][k]+Adj[k][j];}}}}
}int main(){scanf("%d %d",&vNum,&eNum);for(int i=0;i<=vNum;i++){for(int j=0;j<=vNum;j++){Adj[i][j] = inf;}}for(int i=0;i<=vNum;i++){Adj[i][i] = 0;}int v1,v2,dis;for(int i=0;i<eNum;i++){scanf("%d %d %d",&v1,&v2,&dis);Adj[v1][v2] = Adj[v2][v1] = dis;dis;}Floyd();DFS(0);if(visNum!=vNum+1){for(int i=0;i<visNum;i++){printf("%d",path[i]);if(i!=visNum-1)printf(" ");}printf("\n");int pNum = vNum - visNum + 1;for(int i=1;i<=vNum;i++){if(vis[i]==false){printf("%d",i);pNum--;if(pNum!=0)printf(" ");}}}else{for(int i=0;i<visNum;i++){printf("%d",path[i]);if(i!=visNum-1)printf(" ");}printf("\n");printf("%d\n",totalDis);}
}相关文章：
JAVA抽象类和接口的区别【附经典分析用例Door】
这篇文章对抽象类和接口说的很详细，希望对大家有所帮助. abstract class和interface是Java语言中对于抽象类定义进行支持的两种机制，正是由于这两种机制的存在，才赋予了Java强大的面向对象能力。abstract class和interface之间在对于抽象类…
sql 2005提示未能加载包Microsoft SQL Management Studio Package
被360隔离了，请到360恢复区恢复。转载于:https://www.cnblogs.com/janealer/p/4238743.html
puppeteer爬虫的奇妙之旅
(爬虫)[puppeteer|] 爬虫又称网络机器人。每天或许你都会使用搜索引擎，爬虫便是搜索引擎重要的组成部分，爬取内容做索引。现如今大数据，数据分析很火，那数据哪里来呢，可以通过网络爬虫爬取啊。那我萌就来探讨一下网络爬…
(C++)异常退出情况合集(持续更新中)
1.一个有输入的程序，还没做任何输入就自己运行结束了 原因：将长度为10的6次方的整型数组定义在main函数内 2.点击编译运行，显示源文件未编译 原因：定义了一个10的9次方长度的整型数组(虽然在main函数外)
Resin介绍及其使用配置
Resin是一个提供高性能的，支持 Java/PHP 的应用服务器。目前有两个版本：一个是GPL下的开源版本，提供给一些爱好者、开发人员和低流量网站使用；一种是收费的专业版本，增加了一些更加适用于生产环境的特性。 Resin的一些…
Linux基础教程之linux文件权限深度解读
基本命令——来源于马哥教育官网1.cut: cat /etc/passwd | cut -d’:’ -f7| uniq -c| sort -nr 2.authconfig 修改加密方式–passalgosha256 — update3.scp 上传文件-r dir ip:path 传目录file ip:path传文件-P port 指定端口4.rsync 同步文件-avz 源文件 ip:pathscp和rsync都…
浙江大学软件学院2020年保研上机模拟练习 7-4 Shopping With Coupons
目录 解题思路演进过程 第一次程序 第二次程序 第三次程序 解题思路演进过程 首先是题目的理解上：有n个商品，n张优惠券，实际上能买的商品个数最多就是n*n,为啥呢，这题默认是买一个商品必须用一张券，而且一个商品每…
erlang supervisor simple_one_for_one实例
http://www.cnblogs.com/little-ant/p/3196201.html simple_one_for_one vs one_for_one: 相同点： 这种Restart Strategy和one_for_one基本相同(即当一个child process挂掉后，仅仅重启该child process 而不影响其他child process)。 异同点： …
sql isnull函数的使用(转载)
sql isnull函数的使用 ISNULL 使用指定的替换值替换 NULL。 语法 ISNULL ( check_expression , replacement_value ) 参数 check_expression 将被检查是否为 NULL的表达式。check_expression 可以是任何类型的。 replacement_value 在 check_expression 为 NULL时将返回的表达…
Error creating bean with name 'defaultHandlerMapping' defined in ServletContext resource
未解决转载于:https://www.cnblogs.com/hqsbrx/p/9969449.html
priority_queue 结构体的优先级设置
目标：使用结构体Node类型的优先队列，让其按照我们希望的顺序进行排序。 预备知识：会结构体的定义，和结构体类型的优先队列的定义，知道优先队列默认是最大堆排序(即top()得到的是最大的元素) 要做的事：在结…
PNG透明兼容IE6的几种方法
png透明针对IE6一直是件挺麻烦的事情，使用的方法也是各有不同，大多的原理是用IE的滤镜来解决的。 语法：filter : progid:DXImageTransform.Microsoft.AlphaImageLoader ( enabledbEnabled , sizingMethodsSize , srcsURL ) enabled : 可选项。…
ntohs的一个简单实现(将网络流中用两个字节16进制表示的资源数(如DNS)和长度转换为整形)...
我们知道在由于大端机和小端机导致网络字节序和主机序有可能是有差异的，我们可以使用系统的ntohs,ntohl,htons和htonl这些处理函数进行转换，下面是我写的一个关于ntohs在处理小端机字节序转换的函数的简单实现. 思想大致如下: 用u_int16_t的2字节16位的整…
循环获取结构体中的健名与值的实现
为什么80%的码农都做不了架构师？>>> type Person struct {Name stringAge int }func main() {a : &Person{"Name", 1}v : reflect.ValueOf(a).Elem() //a需要是引用k : v.Type()for i : 0; i < v.NumField(); i {key : k.Field(i)…
PAT（甲级）2020年春季考试 7-4 Replacement Selection
这种复杂的模拟题，对于我这种菜鸡，只能是根据自己的理解，去把题目给演示出来，然后结合测试用例，一点一点debug打印输出，的确耗时，所以考试要是遇到就放最后吧。 把这题做出来，我的一…
On/Off FlipSwitch 按钮
https://proto.io/freebies/onoff/转载于:https://www.cnblogs.com/ElvinLong/p/4253665.html
P1541 乌龟棋 题解(洛谷,动态规划递推)
题目:P1541 乌龟棋 感谢大神的题解(他的写的特别好) 写一下我对他的代码的理解吧(哎,蒟蒻就这能这样...) 代码: #include<bits/stdc.h> #define ll long long using namespace std; ll num[350100]; ll p[5]; ll f[41][41][41][41]; int main() {ios::sync_with_stdio(fa…
asp.net 操作excel的实现代码
http://www.cnblogs.com/fywh/archive/2010/01/25/1655864.html转载于:https://www.cnblogs.com/modernsky2003/archive/2010/02/26/1673925.html
PAT（甲级）2020年春季考试 7-2 The Judger
这道题在模拟过程类型题种算友好的，很平铺直叙，主要就是hash的应用。 有两个小点： 1. 怎样快速求两个未知大小的整数a和b的差值(>0) abs(a,b) 2. 如果某一轮有不止一个人淘汰，应该输出 Round #1: 3 is out. Round #1: 4 …
C++_volatile限定修饰符 Pair类型
Volatile限定修饰符 当一个对象的值可能会在编译器的控制或检测之外被改变时，例如一个被系统时间更改的变量，那么这个变量就应该声明成volatile。 其主要作用是提示编译器，该对象的值可能在编译器未检测到的情况下被改变。因此编译器执行的某…
FWFT FIFO读操作注意
FWFT：First Word Fall Through的缩写，好像是Xilinx的说法，Altera对应的概念是Show-ahead synchronous(SASO)。即数据在rdreq有效之前就有效了，rdreq作为一个应答(ACK)。 需要注意的是当rdreq连续时，容易多读一个数据…
iOS图像识别
iOS通过摄像头动态识别图像 前言： 目前的计算机图像识别，透过现象看本质，主要分为两大类: 基于规则运算的图像识别，例如颜色形状等模板匹配方法基于统计的图像识别。例如机器学习ML，神经网络等人工智能方法**区别&…
PAT（甲级）2019年冬季考试 7-4 Cartesian Tree
这道题利用的是最小堆和中序排序的属性：只要知道根节点，就能得出哪些属于左子树，哪些属于右子树。 开始我一直报段错误，经过筛查，发现是创建树的函数忘记写返回语句 return root. AC代码 #include<cstdio> #i…
C#操作excel(多种方法比较)
我们在做excel资料的时候，通常有以下方法。 一.导入导出excel常用方法： 1.用查询表的方式查询并show在数据集控件上。 代码 publicstaticstringstrCon "Provider Microsoft.Jet.OLEDB.4.0 ; Data Source C:\\08.xls;Extended PropertiesExcel 8.0&…
383. Ransom Note/691. Stickers to Spell Word-- String, Map, back tracking-- 未完待续
383 easy 题，就是建立字母的hash 表 看第一个String 是否能被第二个String 所构建 canConstruct("aa", "aab") -> true 统计 第二个参数中每个字母的频率，可以用一个int[256] 建立hashmap, 然后统计 第一个String 中字母出现的…
Centos 修改时间地区及NTP同步北京时间
在我们使用CentOS系统的时候，也许时区经常会出现问题，有时候改完之后还是会出错，下面我们就来学习一种方法来改变这个状况。如果没有安装，而你使用的是 CentOS系统 那使用命令 yum install ntp 然后：ntpdate us.pool.n…
PAT（甲级）2019年冬季考试 7-2 Block Reversing
这题是做过的，B1025，我还总结过，果然早晚复相逢，只改了一点点，见1025 反转链表。 点睛之笔是结构体数组的哈希，地址既做下标，又有实际含义，妙啊。 node[add].add add; 当时应该是…
题目1444：More is better
时间限制：3 秒 内存限制：100 兆 特殊判题：否 提交：1362 解决：640 题目描述：Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the bette…
COMP 0137 Machine Vision
COMP 0137作业代做、Python实验作业代写、代做Python语言程序作业、代写Machine Vision作业COMP 0137 Machine Vision: Homework #1Due 19th November 2018 at 23:55pmWorth 10% of your overall gradeSubmit online, through MoodleFor this homework, we’ll revisit the pra…
windows mobile shell API
SHSetNavBarText 设置NavBar 文本信息 SHDoneButton 设置右上角button为关闭，还是最小化。 SHFullScreen 全屏，显示隐藏taskbar 软键盘button 开始图标 SHInitDialog 实例化对话框 SHInitDialogFlags 设置dialog参数…