Asimple

分类

LeetCode(2) 未归档(188)

/ 注册

全部文章（共7篇）

ACM题目————一笔画问题

描述 zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。规定，所有的边都只能画一次，不能重复画。 <dl class="others"> <dt> 输入 </dt> ...

ACM 数据结构并查集图 DFS

2016-05-26

0 648

ACM第四站————最小生成树（克鲁斯卡尔算法）

都是生成最小生成树，库鲁斯卡尔算法与普里姆算法的不同之处在于——库鲁斯卡尔算法的思想是以边为主，找权值最小的边生成最小生成树。主要在于构建边集数组，然后不断寻找最小的边。同样的题目：最小生成树题目描述求一个连通无向图的最小生成树的代价（图...

ACM 图克鲁斯卡尔

2016-06-01

0 650

ACM题目————最短路径问题

Description 给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 Input 输入n,m，点的编号是1~n,然后是m行，每行4...

ACM 图最短路

2016-07-09

0 676

ACM第四站————最小生成树（普里姆算法）

对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。普里姆算法是以其中某一顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树。其中运用到了回溯，贪心的思想。 ----------2018年5月24日补：　　#b...

ACM 图最小生成树

2016-06-01

0 827

POJ - 3259 Wormholes

Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar bec...

图 bellman_Ford SPFA

2016-12-06

0 484

图论相关之匈牙利算法

这个本来应该是在大一就掌握的算法，硬生生被我拖到现在。。。　匈牙利算法是用来求二分图的最大匹配的一种比较简单的算法，最核心的东西就是找增广路径。详情：http://blog.csdn.net/acdreamers/article/details/8621130 　　记住一些常见的结论： ...

图匈牙利算法

2016-12-21

0 659

hihoCoder 1394 : 网络流四·最小路径覆盖

题目链接：https://hihocoder.com/problemset/problem/1394 题目说是网络流，但是其实就是求有向无环图的最小路径覆盖。不会网络流，只好用二分匹配了。把每个点，拆成入点，和出点，一条路径就是在B块一定是匹配了的，也就是说要求的最小路径覆盖，就是那些没有...

匈牙利算法图

2018-03-27

0 555