2020-07-01 个人训练赛后补题
题目翻译如下：
一个叫Delta的狗子，喜欢讨食。Delta生活在一个有N个建筑物（编号分别为1~N）的城市，有M座建筑物会款待它。而且，有P条路连接着这堆建筑物，每条路连着一栋楼R和一栋楼S。Delta焦虑地待在楼A，想去楼B。如果它遇到没能款待它的建筑物，它会很伤心。Delta希望他能尽可能快地到达目的地。帮助Delta开开心心地从A抵达B吧，并且输出他的路程。
注意：题目保证出发地和目的地都能款待Delta。
##input：
第一行包括T，测试样例数目。每个测试样例如下：
——第一行包括N和M，分别为建筑物总数、能供食建筑物总数
——次行包括M个整数，为供食建筑物编号
——次行包括P，为路的总数
——次P行各包括两个整数，分别为每条路连接的两个建筑物
——次行包括两个整数，分别为出发地建筑物编号A和目的地建筑物编号B
##output：
对每个测试样例，输出单独一行表示Delta旅途的最短路程。如果他不能到达目的地输出-1。
##Constraints：
1<=T<=20
2<=M<=N<=10000
1<=P<=10000
1<=R,S<=N
1<=A,B<=N
A!=B
题目所提供的测试样例：
输入：
1
5 3
1 2 3
7
1 2
1 3
2 4
2 5
4 5
2 3
1 4
1 2
输出：
1
//----------------------------这题当时没写……最小生成树本人不熟，其实道理大概懂一点但会写得很慢很慢，每一个步骤都得想很久【这种速度还不如直接放弃题目】
QAQ我菜炸了
每一次补题都要学一遍啊
//---------------------------补题开始：
由于觉得每次都要一个一个写函数有点奇怪【竞赛怎么也不应该这么打吧？】特地上网搜了一下，发现关键词“最小生成树”和“最小生成树 ACM”的搜索结果是不同的，代码相差也很大。原来大学数据结构课上那种是普通孩子打的代码，不是acm竞赛时用的。其实原理差不多，就是我脑子被上课时学的框架框住了……以为没能比那种更短的，但实际上很多不必要的旁枝末节可以删去。
平日学的专业课程代码只是更好理解算法的原理而已。
下面是补题学习过程中的小笔记【补题补到我这份儿上也是绝了QAQ菜炸了】
Prim算法：【邻接矩阵或表为基础】从某一点开始找一个最近的点，这两个点就是一个集合，然后再找一个距离集合内任一个点最近的点纳入集合（每次把边记好），重复直到所有点都在集合内。【算法T(n)=n*n，与边数无关，适用于稠密图】
Kruskal算法：【森林和树为基础】当所有边和点是分开的两个集合（当图只有点没有边），然后如果加入不会使图成环，就按照权值最小优先的顺序把边塞进图里，直到所有的点都被边连上。【算法T(n)=eloge，与点数无关，适用于稀疏图】
acm中如果思路清晰可尝试用数组替代复杂的结构。
接下来是自己写代码尝试：（prim）由于题目边权值均作1计算，仅需查找同端点边即可，记作边a[i]={s,r}。
以a为出发点，匹配一条边得到集合内第二个点，如果非b则循环，为b退出。(困难：成环情况、断路情况)
起始点a作为集合第一个元素 → 遍历map → 有达标边且不成环且不在集合 → 纳入集合 → 集合当前元素的下一个元素x为b则退出，否则x遍历map → ……（循环）
出来代码是这样的：
不过Wrong了……题目样例可以过，系统测试不通过，大概是集合数据分布和各种奇奇怪怪bug的原因……
1 #pragma warning (disable:4996) 2 #include <iostream> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 #include<string.h> 7 #include<string> 8 #define MAX1 100005 /*1e5 + 5*/ 9 #define MAX2 1000000005 /*le9 + 5*/ 10 #define MAX3 200005 /*1e5 + 5*/ 11 #define MAX4 5005 /*5e3 + 5*/ 12 #define MAX5 10005 /*1e4 + 5*/ 13 #define T1 27 14 #define T2 27 15 #define T3 18 16 using namespace std; 17 typedef long long int ll; 18 #define MOL 998244353 19 20 int main() { 21 int t, n, m, p, a, b; 22 int am[MAX5] = { 0 }; 23 while (scanf("%d", &t) != EOF) { 24 int i, j, k; 25 for (k = 0; k < t; ++k) { 26 scanf("%d %d", &n, &m); 27 int x, min = n, max = 1; 28 for (i = 0; i < m; ++i) { 29 scanf("%d", &x); 30 if (max < x)max = x; 31 if (min > x)min = x; 32 am[x] = 1; 33 } 34 scanf("%d", &p); 35 int s = 0, r = 0; 36 int map[MAX5][2] = { 0 }; 37 for (i = 0, j = 0; i < p; ++i) { 38 scanf("%d %d", &s, &r); 39 if (am[s] && am[r]) { 40 map[j][0] = s; 41 map[j][1] = r; 42 j++; 43 } 44 } 45 int num = j; 46 scanf("%d %d", &a, &b); 47 int fl[MAX5] = { 0 };//标记是否已检测，防止成环和集合重复 48 int jh[2][MAX5] = { 0 };//集合,[0]为检索点,[1]为结果点，实际记录边 49 int rec;//记录当前元素检索出的第几个目标 50 i = 0; 51 jh[1][i] = a; 52 while (jh[1][i]) { 53 rec = 1; 54 for (j = 0; j < num; ++j) { 55 if (map[j][0] == jh[1][i] && fl[map[j][1]] == 0) { 56 fl[map[j][1]] = 1; 57 jh[0][i + rec] = jh[1][i]; 58 jh[1][i + rec] = map[j][1]; 59 rec++; 60 } 61 if (map[j][1] == jh[1][i] && fl[map[j][0]] == 0) { 62 fl[map[j][0]] = 1; 63 jh[0][i + rec] = jh[1][i]; 64 jh[1][i + rec] = map[j][0]; 65 rec++; 66 } 67 if (map[j][0] == jh[1][i] && map[j][1] == b) 68 break; 69 if (map[j][1] == jh[1][i] && map[j][0] == b) 70 break; 71 } 72 if (j == num)break; 73 i++; 74 } 75 printf("%d\n", i); 76 } 77 } 78 return 0; 79 }
心累。
由于这道题耗时太长了。用上课时那种结构体制作结点的法子可行，但不适用竞赛。我时间不够啦，还有一堆题要补……这一题先打个标记，等集训结束了再好好研究吧QAQ
我先去看看别人的代码。
///////////////////////////////////////
有一个大佬用队列做了个bfs函数，头文件巨长【宏定义加内联函数合起来93行不带空行，给大佬跪下了】，数组拉到主函数外面，思路也很巧妙。能treat的建筑物是bool类型数组记录的，其他部分数组也是bool类型【我咋就没想到呢bool快多了】。我对比了一下自己的代码，思路和大佬有重叠也有不同，除了数据类型运用生硬外很多细节我都没注意到……大佬treat数组记录可款待的建筑物，函数处理地图，不是二维数组做哒【扑通一声跪下】。代码差别较大的一点在于每次筛出一个新集合成员大佬都会用min做个处理，确保路径最短【我真的想不到那么节省时间的法子，大佬牛笔！】
别人的代码我就不放出来了。想要的可以根据题号自行搜索
我看了一下codechef上面大佬的代码，和百度上最小生成树关键字上搜出来的又不太一样。之前学习简便法子的时候那位大佬只用了数组【可能是因为例子简单，大佬教的比较基础】，但是codechef上大部分大佬都是用queue系列函数的。
等着周末【集训每周放假时间】我好好补一补队列在这方面的运用叭。
总之我学习的任务还很重啊……
原文：https://www.cnblogs.com/nfyyzz/p/13292751.html
