PAT（甲级）2020年秋季考试 7-4 Professional Ability Test
解题思路：
1.用拓扑排序判断给定的图是否是有向无环图(DAG)
在这个过程当中，对于入度为0的结点，在布尔数组中标记是初始结点
通过入队的结点个数是否等于总个数判断是不是DAG
注意：虽然有队列，但是不需要inq[]数组标记是否入队，当弹出一个元素时，再让计数加一
当一个结点出队，不要把对应的邻接向量清空，不然后面的迪杰斯特拉没法玩orz
2.不是DAG
好办，就分为可以作为起点的结点和不可以的两种情况输出
3.是DAG
加一个超级汇点，让这个汇点连接所有可以作为初始结点的结点，这样就转换成了单源最短路径问题，可以用Dijkstra解决。
但是注意这不是最朴素的Dijkstra
3.1 要记录每个结点的前置结点
然后用深度优先的方式递归输出路径
3.2 拥有第二标尺
完整代码如下(注：考试时没做出来，以下代码仅仅是通过了两个给出的test case)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int maxn = 1010;
const int inf = 1000000000;//即10^9 struct Node{int v;//vertexint s;//scoreint d;//dollar Node(int _v,int _s,int _d):v(_v),s(_s),d(_d){}
};vector<Node> Adj[maxn];int vNum,eNum,qNum,inDegree[maxn] = {0},isStart[maxn] = {0};bool topologicalSort(){queue<int> Q;int num = 0;//入队的总结点数 for(int i=0;i<vNum;i++){if(inDegree[i]==0){Q.push(i);isStart[i] = 1;//i是起始节点 }}while(!Q.empty()){int v = Q.front();Q.pop();for(int i=0;i<Adj[v].size();i++){int u = Adj[v][i].v;inDegree[u] --;if(inDegree[u]==0){Q.push(u);}}num ++;
// Adj[v].clear(); }if(num==vNum)return true;else return false;
}int dis[maxn];
int vou[maxn];int pre[maxn]; void Dijkstra(){int s = vNum;bool vis[maxn] = {0};fill(dis,dis+vNum,inf);dis[s] = 0;fill(vou,vou+vNum,0);for(int i=0;i<=vNum;i++){//每次点亮一个结点 //找当前未点亮结点中距离最近的int v = -1,MIN = inf;for(int j=0;j<=vNum;j++){//到这一步出现了段错误 if(vis[j]==false&&dis[j]<MIN){MIN = dis[j];v = j;}}if(v==-1)return;vis[v] = true;for(int j=0;j<Adj[v].size();j++){int u = Adj[v][j].v;if(dis[u]>dis[v]+Adj[v][j].s&&vis[u]==false){dis[u] = dis[v]+Adj[v][j].s;vou[u] = vou[v]+Adj[v][j].d;pre[u] = v;}else if(dis[u]==dis[v]+Adj[v][j].s&&vou[u]<vou[v]+Adj[v][j].d&&vis[u]==false){vou[u] = vou[v]+Adj[v][j].d;pre[u] = v;}} } }void DFS(int u){//s是起点，u是终点 if(u==vNum){
// printf("%d",u);return;}DFS(pre[u]);if(isStart[u]!=1)printf("->");printf("%d",u);
}int main(){scanf("%d %d",&vNum,&eNum);int v1,v2,s,d;for(int i=0;i<eNum;i++){scanf("%d %d %d %d",&v1,&v2,&s,&d);inDegree[v2]++;Node node = Node(v2,s,d);Adj[v1].push_back(node);}bool tsSuccess = topologicalSort();//拓扑排序成功否if(tsSuccess){//增加一个点，编号为vNum，作为超级源点for(int i=0;i<vNum;i++){if(isStart[i]==1){inDegree[i]++;Node node = Node(i,0,0);Adj[vNum].push_back(node);}} printf("Okay.\n");Dijkstra();scanf("%d",&qNum);while(qNum--){int u;//destinationscanf("%d",&u);if(isStart[u]==1){printf("You may take test %d directly.\n",u);}else{DFS(u);printf("\n");} }}else{printf("Impossible.\n");scanf("%d",&qNum);while(qNum--){int u;scanf("%d",&u);if(isStart[u]==1)printf("You may take test %d directly.\n",u);else printf("Error.\n");} }return 0;
}相关文章：
TestNG:org.openqa.selenium.os.UnixProcess$SeleniumWatchDog错误
在TestNG运行自动化测试用例的时候，浏览器FireFox正确打开，可是在测试用例运行完成后，我调用的是webdriver.quit()关闭程序的，结果却报以下错误： Sep 25, 2014 4:19:32 PM org.openqa.selenium.os.UnixProcess$Seleniu…
项目经理修炼手册 2.1.2 项目经理的基本功
具备以上素质的人，大体上可以算是具有基本的程序员素质了，但是想从程序员成为项目经理，必然还需要有一点进步，那额外的这些素质都有哪些呢？ 曾经有人力资源的朋友问我要人，我介绍了几个技术上很不错的人&am…
CSS3动画过渡的jquery动态弹出框插件
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/w178191520/article/details/84111711 在线演示 本地下载
PAT（甲级）2021年春季考试 7-4 Recycling of Shared Bicycles
解题思路： 先用Floyd算法求出全员最短路径矩阵。 然后使用DFS进行遍历，遍历的原则是就近贪心，对于每一个点先遍历离他最近的未访问点。 记录访问点的个数，同时用数组存放已访问点，如果访问点的个数不等于输入点数1(…
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…