博客首页 → 图论

最新文章列表

[Tarjan强连通分量]hdoj 3836：Equivalent Sets

大致题意：     就是给出一个有向图，求最少加多少条边可以使得这个图中的点两两互相可以到达。   大致思路：     大路边的水题目~~考完试第一天就用一道水题纪念一下吧。     先用Tarjan将原图缩点，分别求出入度为0的强连通分量个数和出度为0的强连通分量个数ans1和ans2。ans1和ans2的最小值就是答案。     要注意整个图只有一个强连通分量的情况   # ...
acm图论hdoj 3836bbezxcy 
暴风雪 评论(0) 有963人浏览 2012-07-21 09:40

[最小费用流]zoj 3308：Move the Knights

大致题意：     一个国际象棋棋盘上有n个马分布在不同的黑色格子上，这些棋子共有三种，“金马”移动的能量损耗是P(row1,col1) x P(row2,col2)，“银马”是P(row1,col1) + P(row2,col2)，铜马是max(P(row1,col1) , P(row2,col2))。现在允许n个棋子中有k个棋子移动一步，求移动的马数量最多时最少能量消耗是多少。   大致思 ...
费用流图论acmzoj 3308bbezxcy 
暴风雪 评论(0) 有1019人浏览 2012-06-15 15:45

[图论多解法]hdoj 3342：Legal or Not

大致题意：     很简单，就是给出一个有向图，判断这个图是否含有环。   大致思路：     正解应该是拓扑排序判断环，不过Tarjan求强联通分量，floyd也可以解。 实验室快关门了，先贴上Tarjan的～～   /* Tarjan算法求强连通分量 */ #include<iostream> #include<cstdio> #in ...
图论taijanfloydhdoj 3342bbezxcy 
暴风雪 评论(0) 有1017人浏览 2012-06-14 22:17

[二分+匈牙利]zoj 3460：Missile

大致题意：    用n个导弹发射塔攻击m个目标。每个发射架在某个时刻只能为一颗导弹服务，发射一颗导弹需要准备t1的时间，一颗导弹从发射到击中目标的时间与目标到发射架的距离有关。每颗导弹发射完成之后发射架需要t2的时间进入下个发射流程。现在问最少需要多少时间可以击毁所有m个目标。   大致思路：    二分枚举这个最大时间的最小值，每次按照这个枚举的时间构出二分图，求最大匹配来判定枚举值是否符合要 ...
zoj 3460图论acm二分图bbezxcy 
暴风雪 评论(0) 有1271人浏览 2012-05-26 16:16

[最小费用流 || KM算法]hdoj 3395：Special Fish

大致题义：     给出n条鱼之间相互攻击的关系以及每条鱼的能量值，每条鱼只能攻击或者被攻击最多一次（也就是被攻击之后无法攻击别人，或者攻击别人之后无法被攻击）。一次攻击行为产能为这两条鱼能量值的异或值。求总能量值最大是多少。   大致思路：     用KM算法，把每条鱼拆做两个点，连别求最大匹配的思路很容易想到，代码如下。 #include<cstdio> #include ...
最小费用流KM算法hdoj 3395bbezxcy图论 
暴风雪 评论(0) 有1358人浏览 2012-05-04 10:54

[点双连通分量]hdoj 3394：Railway

大致题意：    给出一个无向图，求出割边的条数，并求出存在在多个环中的边的条数。   大致思路：     先给出题人跪了，真的没想明白为什么circuit是点双连通分量的意思，用边双连通分量wa了一上午。知道了是点双连通分量，问题就简单了，如果一个circuit中的点数小于边数，那么这个分量中所有的边肯定是多余的。   #include<iostream> #incl ...
hdoj 3394acmbbezxcy图论数据结构 
暴风雪 评论(0) 有1588人浏览 2012-05-01 14:03

[一般图最大匹配]URAL 1099：Work Scheduling

大致题意：    给出n个士兵，再给出多组士兵之间两两可以匹配的关系。已知某个士兵最多只能与一个士兵匹配。求最多能够有多少对匹配，并输出这些匹配。   大致思路：     最大匹配问题，对于二分图来说用的是匈牙利算法，求一般图最大匹配用的是带花树开花算法。这里面要注意一点，输出匹配时，要把match[i]和match[match[i]]同时设为-1。   #include <i ...
一般图最大匹配URAL 1099acm图论bbezxcy 
暴风雪 评论(0) 有3141人浏览 2012-04-17 08:39

[传递闭包+SPFA最长路判正环]poj 1932：XYZZY

大致题意：     给出一个由n个房子，由若干的单向路连接起来，每个房子都有一个权值，意味着进入这个房子得到或者消耗的能量。把你放在1点，给你100点的初始能量。现在问你能否到达n点且到达时权值大于0.   大致思路：    很好的题目，参考了小媛神的思路 Orz。首先用spfa求最长路，同时判定是否存在正圈，再用floyd求出传递闭包。如果spfa求出的dis[1,n]大于0。或者从起点可以 ...
图论spfaacmpoj 1932bbezxcy 
暴风雪 评论(0) 有2185人浏览 2012-04-13 12:03

[SPFA+精度控制]hdoj 1245：Saving James Bond

大致题意：    给出一个100*100的池塘，池塘中心位于二维坐标原点。池塘中心有一个直径为15的圆形岛屿，一个人站在岛屿上。给出池塘中n个小岛的位置和这个人的最大步长。求这个人想到池塘对岸的话最少要走多长的距离，最少要迈多少步。   大致思路：    把小岛抽象为起点，对岸抽象为终点，求最短路即可。最短路的思路很好想到，但是需要精度控制的经验啊。     #include<ios ...
SPFA最短路hdoj 1245图论acm 
暴风雪 评论(0) 有1222人浏览 2012-04-10 21:14

[SPFA]hdoj 3790：最短路径问题

大致题意：    给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。   大致思路：    最短路稍稍变形，加入一个val限制即可   #include<iostream> #include<cmath> #include<cstdio> #inc ...
最短路图论acmhdoj 3790bbezxcy 
暴风雪 评论(0) 有2403人浏览 2012-04-07 19:20

[无向图全局最小割]zoj 2753：Min Cut (Destroy Trade Net)

大致题意：    给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。   大致思路：     裸的StoerWagner模版题，在神牛的博客瞎逛的时候看到了，就刷掉吧……希望不要降RP     #include<iostream> #include<cstdio> #include<cstring> using namespace s ...
无向图全局最小割zoj 2753acm数据结构图论 
暴风雪 评论(0) 有1882人浏览 2012-04-02 17:11

[点双连通分量-奇环判定]poj 2942：Knights of the Round Table

大致题意：     给出一个无向图，求出这个图的补图G。求出在G中存在多少个点使得这些点不属于任何一个奇环中。   大致思路：    这道题从一开始就是个杯具！先是把题目想成边的双连通分量做，狂哇。后来用割点的模版照着网上的代码改造出一个点双连通分量的代码，依然哇！！原因是同一个点可能属于不同的点双连通分量！！   后来把搜索染色的过程加到Tarjan里面，还是哇！！检查出来原因是搜索u的时候 ...
点双连通分量poj 2942acm数据结构图论 
暴风雪 评论(0) 有2558人浏览 2012-03-30 22:14

[网络流]hdoj 3251：Being a Hero

大致题意：    给出一个由n个点，m条边组成的有向图，给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开，同时你会得到相应的收益值。求总收益的最大值。   大致思路：     网络流经典构图……   #include<iostream> #include<cstring> #include<cstdio&g ...
网络流hdoj 3251acm数据结构图论 
暴风雪 评论(0) 有1121人浏览 2012-03-22 16:15

[最小割]hdoj 2435：There is a war

大致题意：    给出一个有向带权图，设1为源点，n为汇点。现在要在2~n-1的点中加上一条容量为无穷的边使得这个图的最小割最大。求加上这条边后最小割最大是多少。   大致思路：    先对原图求一遍最小割，割值为maxflow，在残余网络中分别找到两个点a,b，使得从1点到a的最大流值最大，为flowA，从b点到n点的最大流最大，为flowB。然后用maxflow+min(flowA,flow ...
最小割hdoj 2435acm数据结构图论 
暴风雪 评论(0) 有1071人浏览 2012-03-19 14:21

数学之美系列六：图论和网络爬虫 (Web Crawlers)

发表者: 吴军，Google 研究员 [离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。 ...
图论网络爬虫Web Crawlers 
abc123456789cba 评论(0) 有1159人浏览 2012-03-10 21:18

[差分约束]hdoj 3666：THE MATRIX PROBLEM

  大致题意：     给出一个n*m的矩阵map，和两个数字L，U。求出是否存在这样的数列a[1~n]，b[1~m]。使得对于每一个map[i][j]有map[i][j]*a[i]/b[j]大于等于L，小于等于U。   大致思路：     用log运算把乘法转化为加法，求出不等式。然后做差分约束。另外注意一点，如果直接用每个点入队次数大于n来判定的话肯定会超时。     在牛人博客 ...
差分约束hdoj 3666acm数据结构图论 
暴风雪 评论(1) 有1207人浏览 2012-03-10 19:54

[Tarjan 有向图强连通分量]ural 1198：Jobbery

大致题意：  给出一个有向图，求图中是否存只在一个入度为0的强联通分量，存在的话输出这个分量中的所有点。否则只输出一个 0.   大致思路：    Tarjan缩点，后对所有强连通分量求出入度出度~~   #include<iostream> #include<cstdio> #include <algorithm> #include<c ...
Tarjan强连通分量ural 1198图论acm 
暴风雪 评论(0) 有1499人浏览 2012-03-10 11:49

[二分匹配]poj 2724：Purifying Machine

大致题意：     给出m串长度为n的01串。有些串中可能包含*，这样的串可以表示两个串，*为1 和*为0。重复的算一种。比如题目中 *01 100 011 就代表了四个01串 001 101 100 011 现在我们需要消灭掉所有的01串，消灭方式有两种： 1一次消灭一个串。 2如果两个串的差别只有一位的话可以同时消灭这两个串。   问最少多少次操作可以消灭所有的01串 ...
二分匹配poj 2724图论acm数据结构 
暴风雪 评论(0) 有1542人浏览 2012-03-05 13:57

[最小费用流]hdoj 2282：Chocolate

大致题意：     有n个巧克力盒子摆成一圈，每个盒子中装有一定数量的巧克力，所有盒子中的巧克力的总数小于n。现在每次可以把一块巧克力从一个盒子移动到其相邻的盒子中，求最少移动几部才能使得每个盒子中最多只有一个巧克力。   大致思路：    很经典的构图。设源汇点，将每个盒子拆为两点a，a'。从源点想s连边，容量为盒子中巧克力的数量，费用为0。从         a->b'连边，容量为1 ...
最小费用流hdoj 2282acm数据结构图论 
暴风雪 评论(0) 有1191人浏览 2012-02-10 20:02

最近博客热门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