HBUACM

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。 输入格式:输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。 输出格式:按照”{ v1 v2 … v**k }”的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。 输入样例:12345678 60 70 12 04 12 43 5结尾无空行 输出样例:123456{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }结尾无空行 思路就是简单的dfs和bfs。vis数组(visited)存储是否已经搜索过，vis[idx]=1表示已经idx已经搜索过，vis[idx]=0表示还没有搜索过。 代码123456789101112131415 ...

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。 可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。 这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？ 输入格式:输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。 输出格式:若欧拉回路存在则输出1，否则输出0。 输入样例1:12345678910116 101 22 33 14 55 66 41 41 63 43 6结尾无空行 输出样例1:123451结尾无空行 输入样例2:1234567895 81 21 32 32 42 55 35 43 4 输出样例2:10 思路无向图存在欧拉回路的两个条件： 该图是连通图。 每个顶点的度是偶数。 对于是否连通，使用广 ...

LC 在他小时候特别迷恋绝地求生，他就幻想着有一天能被扔到一个孤岛，他想算出整个岛屿的面积。 简化题意为一个 n∗n 的地图，共有 n∗n 个面积为 1 格子，地图左上角的格子编号为 (1,1) 右下角的格子编号为为 (n,n) 。地图上为每个格子做了标记，若编号为 (x,y) 的格子标记位 0 则代表这个区域是海，否则为陆地。 现在 LC 空投到 (sx,sy) 位置，他想知道他所在的岛屿的面积。 注意，可能不止一个岛屿，只用求 LC 所在的岛屿面积。 输入格式:第一行给出一个正整数 n(1<=n<=50) 表示地图的大小为 n∗n 第二行给出两个正整数 sx,sy 表示 LC 空投到的位置 之后的 n 行，每行给出 n 个整数。其中的第 i 行第 j 列的整数若为 0 则代表编号 (i,j) 位置是海洋，否则代表陆地。 保证数据一定合法，且 LC 不会落在海里。 输出格式:在一行中输出 LC 所在岛屿的面积。 输入样例:1234567865 30 0 0 1 1 01 0 0 1 1 00 0 1 0 1 11 1 0 1 0 10 1 1 1 0 11 1 0 1 1 ...

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。 输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。 输出格式:在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。 输入样例:1234564 5 0 30 1 1 201 3 2 300 3 4 100 2 2 202 3 1 20结尾无空行 输出样例:123453 40结尾无空行 思路两个权值的最短路径问题。当路径长度不相同时，我们要最短的；当路径长度相同时，我们要花费最少的。 G存储距离，cost存储花费。lowcost[ idx ] [0 ...

请编写程序创建一个有向图。有向图中包含n个顶点，编号为0至n-1。 输入格式:输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。 输出格式:按顶点编号递增顺序输出每个顶点引出的边，每个顶点占一行，若某顶点没有引出边，则不输出。每行表示一个顶点引出的所有边，格式为a:(a,b,w)……，表示有向边a->b的权值为w，a引出的多条边按编号b的递增序排列。 输入样例:123456787 70 1 50 3 70 6 61 2 42 5 13 5 36 5 4结尾无空行 输出样例:123450:(0,1,5)(0,3,7)(0,6,6)1:(1,2,4)2:(2,5,1)3:(3,5,3)6:(6,5,4)结 尾无空行 思路算法1 邻接表这里的链表采用的是包含头节点的形式，方便插入。插入的时候有序的插入，方便输出。 算法2 vector其实也是邻接表的思路，只不过每个节点的邻接点没有用链表存储，用的vecto ...

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。 输入格式:输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N；随后的M行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到N）以及该道路改建的预算成本。 输出格式:输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。 输入样例1:123456789101112131415166 151 2 51 3 31 4 71 5 41 6 22 3 42 4 62 5 22 6 63 4 63 5 13 6 14 5 104 6 85 6 3结尾无空行 输出样例1:1234512结尾无空行 输入样例2:123455 41 2 12 3 23 1 34 5 4 输出样例2:1Impossible 思路prim 代码 ...

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？ 但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。 输入格式：输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。 输出格式：对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。 输入样例：12345678910111213146 8 32 11 34 62 52 45 45 63 641 2 3 3 1 24 5 6 6 4 51 2 3 4 5 62 3 4 2 3 4结尾无空行 输出样例：12 ...

河北大学暑期程序设计训练每日知识分享-day22 每日分享——GitHubGithub https://github.com/GitHub 是一个面向开源及私有 软件项目的托管平台，因为只支持 Git 作为唯一的版本库格式进行托管，故名 GitHub，其社交化编码的理念伴随着开源运动改变着整个开发社区的生态，无数优质项目依托GitHub在全球开源开发者的参与下蓬勃发展。 GitHub 于 2008 年 4 月 10 日正式上线，除了 Git 代码仓库托管及基本的 Web 管理界面以外，还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱（报表）、代码片段分享（Gist）等功能。目前，其注册用户已经超过350万，托管版本数量也是非常之多，其中不乏知名开源项目 Ruby on Rails、jQuery、python 等。 2018年6月，GitHub被微软以75亿美元的价格收购。 GitHub用户可以在GitHub上创建自己的仓库，将本地的文件、项目等上传至仓库，可以永久存储，并且可以设置仓库为私有或公有，私有状态下只有自己可以访问，同时可以利用github pages创建自己的网站， ...

河北大学暑期程序设计训练每日知识分享-day21 每日分享——康托展开&逆康托展开定义康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。 设有n个数（1,2,3,4,…,n）,组成不同 n! 种的排列组合，其康托展开唯一且最大约为n!康托展开表示的就是当前排列在n个不同元素的全排列中的名次。时间复杂度O(n^2^) 适用范围搜索，动态规划中常常用一个数字来表示一种状态，大大降低空间复杂度 公式X=a1×(n?1)!+a2×(n?2)!+?+an×0!X代表当前排列在全排列中的排名，ai 代表当前数是数列中未出现的数中第几小的 从0开始计数，0是第一小的数 例如 4,2,3,14,2,3,1 4 是当前数列中未出现的数中第3 小的，X+=3?(4?1)! 2 是当前数列中未出现的数中第1 小的，X+=1?(4?2)! 3 是当前数列中未出现的数中第1 小的，X+=1?(4?3)!,因为22 已经输出过了，所以不算 1 是当前数列中未出现的数中第0 小的，X+=0?(4?4)!这要就求出了4,2,3,14,2,3,1 所唯一对应的在全排列中的名次X=22 注 ...

河北大学暑期程序设计训练每日知识分享-day20 每日分享——C++集合操作set函数求并集、交集、差集、对称差集beg1，end1容器1的开始、结束迭代器，beg2，end2容器2的开始、结束迭代器 求交集set_intersection() 函数原型：set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest) 作用：将容器1和容器2的交集存到目标容器，dest为目标容器的起始迭代器。 求并集set_union() 函数原型：set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest) 作用：将容器1和容器2的并集存到目标容器，dest为目标容器的起始迭代器。 求差集set_difference() 函数原型：set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator ...