HBUACM

河北大学暑期程序设计训练每日知识分享-day24 每日分享——0x3f3f3f3f在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。 比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。 而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。 所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处： 0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9^数量级，而一般场合下的数据都是小于10^9^的。 0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。 可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。 memset函数是把array的每个字节都赋值成第二个参数（因为他的头文件是cstring嘛)，一个int数字,每个字节都 ...

河北大学暑期程序设计训练每日知识分享-day23 每日分享——可保存多次复制内容-Ditto可以保存多次复制内容的软件，Ditto Ditto是剪贴板增强工具，免费开源且支持中文（开源就是说大概率能在github找到这个软件的源代码，可以下载下来自己魔改自己用）保存多次复制的内容，打开近期内容面板后选择一个用于粘贴，包括图片等非文字格式的复制也可，可以自己设置保存多少条近期复制的信息和一些快捷键避免在做题调试代码时重复的复制测试点、复制代码提交 软件安装包见群文件。 小彩蛋：STL中的next_permutation()函数可以计算全排列，示例如下。

请编写程序创建一个有向图。有向图中包含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 ...

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 ...

给定一个有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 ...

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。 输入格式:输入说明：输入数据的第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 (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 ...

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。 可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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 思路无向图存在欧拉回路的两个条件： 该图是连通图。 每个顶点的度是偶数。 对于是否连通，使用广 ...

河北大学暑期程序设计训练每日知识分享-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创建自己的网站， ...