博客首页 → 图论

最新文章列表

hoj 经典最短路 回家

/*这道题很不错，推荐下。貌似也是工大原创的题吧。题意大概就是给一个图。城市和城市之间有边权，从一个城市到一个城市需要转车，也有点权， 而这个值需要取决于该节点的前一条边和后一条边的交通方式。求这样一种情况下的最短路。 这样的请看下需要增加一维来记录交通方式的选择。其余的和dij是一样的。 还有可以用map来记录重复的字符串。*/ #include <iostream> #incl ...
图论 
zhuchuanshua 评论(0) 有2人浏览 2012-08-29 12:28

[最大流]zoj 3642：Just Another Information Sharing Problem

大致题意：      有n个人，每个人知道ai个消息，并且会向周围人最多透露bi个消息。现在问对于一个人x，他最多能知道多少消息。   大致思路：     网络流，分别把消息和人抽象成点，从始点向每个消息连边，容量为1，每个消息都向知道这条消息的人连边，容量也是1.每个人都连向x，容量为他最多透露的消息数。求出最大流即可。   #include<iostream> # ...
图论acmzoj 3642bbezxcy 
暴风雪 评论(0) 有1161人浏览 2012-08-28 13:26

Frogger 最短路变种

/*注意细节。memset里面的0x7f和常数赋值的0x7f差别很大。常数赋值的数值很小。而memset内部是按照字节进行赋值。是一个很大的值。 这一道题是一道最短路的变种。实际上是求所有路径中最大边的最小值。 起点是1，终点为2.*/ #include <stdio.h> #include <cstring> #include <cmath> #inclu ...
图论 
weiwo1978 评论(0) 有5人浏览 2012-08-27 15:30

图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。

图论小结（一） 下面是对暑假集训的图论部分的一些总结和体会。 包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。 下面就暑假写过的一些题做一个小结。 （1）最短路的话一个主要掌握三个算法和两个优化。Dijsktra单源最短路，可以变形他的松弛条件，而产生很多的最短路变种，题型非常灵活 ...
图论 
kulunjingmian 评论(0) 有4人浏览 2012-08-27 15:10

Frogger 最短路变种

/*注意细节。memset里面的0x7f和常数赋值的0x7f差别很大。常数赋值的数值很小。而memset内部是按照字节进行赋值。是一个很大的值。 这一道题是一道最短路的变种。实际上是求所有路径中最大边的最小值。 起点是1，终点为2.*/ #include <stdio.h> #include <cstring> #include <cmath> #inclu ...
图论 
aixiaodeyanq 评论(0) 有5人浏览 2012-08-27 12:02

图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。

图论小结（一） 下面是对暑假集训的图论部分的一些总结和体会。 包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。 下面就暑假写过的一些题做一个小结。 （1）最短路的话一个主要掌握三个算法和两个优化。Dijsktra单源最短路，可以变形他的松弛条件，而产生很多的最短路变种，题型非常灵活 ...
图论 
teseyinzhi 评论(0) 有4人浏览 2012-08-27 11:43

Poj 2240 Arbitrage

题目描述： 套汇是利用汇率之间的差异，从而将一单位的某种货币，兑换回多于1 单位的同种货币。例 如，假定1 美元兑换0.5 英镑，1 英镑兑换10.0 法郎，1 法郎兑换0.21 美元，那么，在兑换货币 过程中，一个聪明的商人可以用1 美元兑换到0.5 * 10.0 * 0.21 = 1.05 美元，这样就有5%的利润。 你的任务是编写程序，读入货币之间的汇率列表，判断是否存在套汇。 输入描述： 输 ...
图论 
wangwangzhi 评论(0) 有5人浏览 2012-08-23 11:07

Poj 2240 Arbitrage

题目描述： 套汇是利用汇率之间的差异，从而将一单位的某种货币，兑换回多于1 单位的同种货币。例 如，假定1 美元兑换0.5 英镑，1 英镑兑换10.0 法郎，1 法郎兑换0.21 美元，那么，在兑换货币 过程中，一个聪明的商人可以用1 美元兑换到0.5 * 10.0 * 0.21 = 1.05 美元，这样就有5%的利润。 你的任务是编写程序，读入货币之间的汇率列表，判断是否存在套汇。 输入描述： 输 ...
图论 
gechanggluo 评论(0) 有7人浏览 2012-08-23 00:10

Poj 1135 Domino Effect(Dijkstra)

题目描述： 你知道多米诺骨牌除了用来玩多米诺骨牌游戏外，还有其他用途吗？多米诺骨牌游戏：取一 些多米诺骨牌，竖着排成连续的一行，两张骨牌之间只有很短的空隙。如果排列得很好，当你推 倒第1 张骨牌，会使其他骨牌连续地倒下（这就是短语“多米诺效应”的由来）。 然而当骨牌数量很少时，这种玩法就没多大意思了，所以一些人在80 年代早期开创了另一个 极端的多米诺骨牌游戏：用上百万张不同颜色、不同材料的骨牌拼成 ...
图论 
rumenglingr 评论(0) 有4人浏览 2012-08-20 17:11

hdu 3080 The plan of city rebuild

The plan of city rebuild Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 583    Accepted Submission(s): 201 Problem Description ...
图论 
juliufeifei 评论(0) 有9人浏览 2012-08-20 12:23

Poj 1679 The Unique MST

题目描述： 给定一个连通无向网，判定它的最小生成树是否唯一。 输入描述： 输入文件的第1 行为一个整数t，1≤t≤20，表示测试数据的数目。每个测试数据描述了一个 连通无向网。每个测试数据的第1 行为两个整数：n 和m，1≤n≤100，分别表示顶点的数目和 边的数目。接下来有m 行，每行为一个三元组(xi, yi, wi)，表示一条边(xi, yi)，xi 和yi 表示边的两 个顶点，顶点序号从1 ...
图论 
chuilengqi 评论(0) 有9人浏览 2012-08-18 15:00

HDU 1241 Oil Deposits DFS

题意：N*M的图中有一些'@',从该位置往四周8个位置延伸，求几块互不连通的‘@’构成的块。简单的DFS便能搞定 import java.util.Scanner; public class Main{ static int m,n; static char[][] arr=new char[101][101]; public static void main(String ...
DFS图论java 
believexkx 评论(0) 有842人浏览 2012-08-17 22:06

Poj 1861 Network (模版kruskal)

题目描述： Andrew 是某个公司的系统管理员，他计划为他的公司搭建一个新的网络。在新的网络中，有 N 个集线器，集线器之间可以通过网线连接。由于公司职员需要通过集线器访问整个网络，因此 每个集线器必须能通过网线连往其他每个集线器（可以通过其他中间集线器来连接）。 由于有不同长度的网线可供选择，而且网线越短越便宜，因此Andres 所设计的方案必须确保 最长的单根网线的长度在所有方案中是最小的。并 ...
图论 
sansuzi88 评论(0) 有6人浏览 2012-08-17 11:54

Poj 1861 Network (模版kruskal)

题目描述： Andrew 是某个公司的系统管理员，他计划为他的公司搭建一个新的网络。在新的网络中，有 N 个集线器，集线器之间可以通过网线连接。由于公司职员需要通过集线器访问整个网络，因此 每个集线器必须能通过网线连往其他每个集线器（可以通过其他中间集线器来连接）。 由于有不同长度的网线可供选择，而且网线越短越便宜，因此Andres 所设计的方案必须确保 最长的单根网线的长度在所有方案中是最小的。并 ...
图论 
mianyou556 评论(0) 有8人浏览 2012-08-17 10:38

[Tarjan变形]zoj 3630：Information

大致题意：    给出一个有向图，现在要删去一个点使得剩下的图中含有点数最多的强连通分量最小。   大致思路：    枚举删点，每次求一遍强连通分量即可   #include<iostream> #include<cstdio> #include <algorithm> #include<cstring> using namesp ...
图论acmzoj 3630bbezxcy 
暴风雪 评论(0) 有1170人浏览 2012-08-15 16:42

网络最大流之一般增广路方法------Ford-Fulkerson

      在该算法中，寻找增广路和改进网络流的方法称为标记法。        对于标记的过程不多加阐述，以下对标记的程序实现做下小小总结： 1：在程序中需要定义三个数组变量分别是flag[],prev[],alpha[]，其中：  flag[]表示顶点的状态，其元素取值及其含义为：-1表示未标号，0表示已标号未检查，1表示已标号已检查  prev[]为标号的第一个分量：指明标号是从 ...
图论 
deng_dai_shi 评论(0) 有13人浏览 2012-08-15 12:43

HDU 3549 Flow Problem 解题报告（EK）算法

转载请注明出处：http://write.blog.csdn.net/postlist 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549 这是一题裸的网络流题目。说有1000条边，可是只有十五个点，所以实际的边数最多只有15*15。EK复杂度O(VE2)，5秒的时间、太多了！
图论 
hongqiang 评论(0) 有986人浏览 2012-08-12 16:45

HDU 3549 Flow Problem 解题报告（EK）算法

转载请注明出处：http://write.blog.csdn.net/postlist 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549 这是一题裸的网络流题目。说有1000条边，可是只有十五个点，所以实际的边数最多只有15*15。EK复杂度O(VE2)，5秒的时间、太多了！
图论 
juliufeifei 评论(0) 有11人浏览 2012-08-12 01:20

POJ 1556 The Doors (计算几何+dij最短路)

好题啊好题！ 一个10*10的房间里，有n堵墙。每堵墙有两扇门，求最短路经 先枚举门的端点，在判断端点连线是否有与其他墙相交，构图，最后dij求最短路！思路一定要清晰。 最后，这题的数组最好开大点。不要天真的以为它只有9堵墙。。它有18堵啊有木有！！ //Memory: 528K //Time: 0MS #include <iostream> #include & ...
图论 
chuilengqi 评论(0) 有14人浏览 2012-08-10 12:45

poj 1258 prim最小生成树

#include <iostream>using namespace std;int a[105][105],b[105],n;int prim(int ii){ int i,j,k,min,ans=0,t; for(i=0;i<n;i++) b[i]=a[ii][i]; b[ii]=-1; for(i=1;i<n;i++) { ...
图论 
leili 评论(0) 有776人浏览 2012-08-07 22:39

最近博客热门TAG

Java(141744) C(73651) C++(68608) SQL(64570) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54784) Web(54511) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40811) 编程(39454) Windows(39381) JSP(37540) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics