博客首页 → 图论

最新文章列表

邻接表无向图-- Java

邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。 上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点的邻接点的序号&qu ...
java邻接表图论数据结构 
wbj0110 评论(0) 有550人浏览 2016-08-26 17:22

Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minim ...
图论 
KickCode 评论(0) 有723人浏览 2016-02-29 04:11

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pai ...
图论 
KickCode 评论(0) 有544人浏览 2016-02-20 05:51

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pai ...
图论 
KickCode 评论(0) 有478人浏览 2016-02-20 03:08

【数据结构】【图论】【最小生成树】Kruskal算法

一、Kruskal算法核心 Kruskal算法和Prime算法一样也是计算最小生成树的一种算法。考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 算法演示   ...
数据结构图论最小生成树Kruskal算法 
狂盗一枝梅 评论(0) 有1359人浏览 2016-01-24 10:41

【数据结构】【图论】【最小生成树】Prime算法

一、问题 最小生成树解决的问题如下所示：        假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？        使用Prime算法构造最小生成树，将生成树上的边的权值累加即可得到最小值。 二、Prime算法核心思想        取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在 ...
数据结构Java图论最小生成树Prime算法 
狂盗一枝梅 评论(0) 有1731人浏览 2016-01-23 18:06

【数据结构】【图论】DFS

      DFS(Depth-First-Search),中文名称为“深度优先搜索”,是纵向遍历图的一种递归算法。       需求：输入edgeCount、startNode，然后输入edgeCount组数据，每组数据有两个数node1与node2，表示一条无向边，最后使用DFS算法输出遍历图的结果，数和数之间使用空格隔开。 一、Java代码 import java.util.Scan ...
数据结构图论DFS 
狂盗一枝梅 评论(0) 有925人浏览 2016-01-23 13:16

zoj 1655 Transport Goods （Dijkstra）

ZOJ Problem Set - 1655 Transport Goods    结题报告： 一开始用的是从首都向其他城市搜索，记录路径，然后向回搜索，但是出现了wa。 后来搜了一下结题报告，别人都是直接搜索，使费用率最大，试了一下，这样做还是wa 最后看了 小媛 的，才知道是可能同时出现费用率不同的同一条路，这是后我们当然要选择费用率较小的 感觉自己第一遍记录路径代码可以过！，但是 ...
zoj 1655最短路图论wa注意 
ren_hui 评论(0) 有943人浏览 2013-11-17 22:26

poj 2421 Constructing Roads (kruskal) runtime error

链接：http://poj.org/problem?id=2421   #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define maxn 210 #define maxm (210*210) using namespace ...
kruskal图论一些简单优化 
ren_hui 评论(0) 有884人浏览 2013-10-30 21:51

poj 2935 (bfs+路径)

题目链接：http://poj.org/problem?id=2935   解题报告：刷到bfs明显的感觉有些难，这道题应该卡的有3~4天了吧！ 首先说明一下bfs如何记录路径：在结构体中，用一个值来记录上一个的位置，然后再“回溯”（并不是真的回溯）到第一个元素，然后递归输出即可； 第二点：交换两个数的位运算方法：a^=b^=a^=b,看上去显得代码更有技术含量 第三点：注意输入值的顺序 ...
bfs记录路径图论搜索 
ren_hui 评论(0) 有1461人浏览 2013-10-08 21:55

zoj 1091 (bfs搜索)

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=91   结题报告：因该说10多天没有A题了，今天过了一道比较水的题目，也算是来纪念一下吧，最近在刷搜索的时候感觉bfs有些题目是比较难的，象蛇和梯子那道题整整卡了我一个星期但是现在仍然没有过，标记一下，有时间在回来看一下！ 这道题注意两个地方，一个是下标的值，一个是v ...
bfs搜索图论象棋中的马的问题 
ren_hui 评论(0) 有1751人浏览 2013-09-28 21:25

Farm Irrigation zoj 2412(dfs)

Farm Irrigation Time Limit: 2 Seconds      Memory Limit: 65536 KB Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes a ...
dfs图论 
ren_hui 评论(0) 有1032人浏览 2013-09-12 19:30

java 图论二 有向图 拓扑排序

有向图的拓扑排序，能够获得访问到某一节点的提前条件。 拓扑排序时不可以实现环和图的拓扑排序。   写一下拓扑排序的实现： 是在联通矩阵上实现的，拓扑排序的算法是： 1.查看连通矩阵是否还有剩余节点，如果有继续2,3操作，如果没有结束拓扑排序 2.找到没有后继的节点 3.如果找到了，从联通矩阵中删除；如果没找到，则此联通矩阵不是DAG，不能进行拓扑排序 package com.C ...
java图论有向图拓扑排序 
blackproof 评论(1) 有4036人浏览 2012-11-21 09:33

java 图论一 深度遍历和广度遍历

图对建模很有帮助。   图的基本知识：   Java实现图的两种方法 1 邻接矩阵 邻接矩阵是用二维数据,使用1代表节点间有边，如下表格：   A B C D
java图论深度遍历思路广度遍历思路 
blackproof 评论(1) 有6411人浏览 2012-11-15 17:43

[二分匹配]zoj 3156：Taxi

大致题意：    有n个人和m辆车(n<=m)。给出所有人和车的坐标，以及人移动的速度。现在让每个人走去找一辆车坐。每辆车只能乘坐一个人，花费的时间最少是多少。   大致思路：    二分这个时间的最大值tmax，再用匈牙利算法判定是否n个人都能在tmax的时间内赶到车上。     一开始直接二分距离，高精度神马的写渣了。后来发现，二分枚举距离值的下标就可以~~   #incl ...
图论zoj 3156acmbbezxcy 
暴风雪 评论(0) 有1184人浏览 2012-10-25 19:28

[Tarjan]uva 4846：Mines

大致题意：     给出n个地雷，每颗地雷有一个爆炸范围，这颗地雷爆炸后，这个范围内的地雷都会炸。求最少引爆多少地雷能使得所有的地雷都爆炸。   大致思路：     把每个地雷看作点，每颗地雷都向其能引爆的地雷连边。建图完成后用Tarjan缩点，求出出度为0的强连通分量的个数就是答案。   #include<iostream> #include<cstdio&g ...
uva 4846bbezxcyacm图论 
暴风雪 评论(0) 有1322人浏览 2012-10-19 10:07

[2-sat][位运算]zoj 3656：Bit Magic

大致题意：    给出下面一段代码     很明显这段代码是用a[n]数组来计算出b[n][n]。 void calculate(int a[N], int b[N][N]) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) b[i][j] = 0; el ...
acmzoj 3656bbezxcy2-sat图论 
暴风雪 评论(0) 有2059人浏览 2012-10-15 09:17

[二分匹配]zoj 3646：Matrix Transformer

大致题意：   给出一个n*n的矩阵，每个矩阵元素的U或者是D。 例如 DUD UDD DDU 每次操作，可以交换任意两行或者两列。求是否能使得其主对角线上的元素全部变成U。   大致思路：     仔细思考就能发现，问题可以转化为，能否找出n个‘U’，使得他们之间两两的行数和列数都不相同。于是就很容易就能构造出二分匹配模型了。   #include<i ...
二分匹配zoj 3646bbezxcyacm图论 
暴风雪 评论(0) 有1067人浏览 2012-10-10 21:15

[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292：Food

大致题意：     有F种食物和D种饮料，每种食物或饮料只能供有限次，且每个人只享用一种食物和一种饮料。现在有n头牛，每个人都有自己喜欢的食物种类列表和饮料种类列表，问最多能使几个人同时享用到自己喜欢的食物和饮料。   大致思路：     把人给拆点，把食物和水的点放在人的两侧 求出s到t的网络流即可     #include<iostream> #include& ...
成都网络赛acm网络流bbezxcy图论 
暴风雪 评论(11) 有2344人浏览 2012-09-16 17:15

[floyd+Tarjan]zoj 3232：It's not Floyd Algorithm

大致题意：     给出一个有向图的传递闭包矩阵，求出这个图至少有多少条边。   大致思路：     对这个图先用Tarjan缩点，再对缩点后的图求一遍floyd求出至少需要多少条边。   #include<iostream> #include<cstdio> #include <algorithm> #include<cstring ...
acmzoj 3232图论bbezxcy 
暴风雪 评论(0) 有1151人浏览 2012-09-09 09:49

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics