beckyUp

图论

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 动态规划(18) 区间dp(3) 博弈(2) 后缀数组(1) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数据结构(22) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算几何(5) 计算方法(4) 读书笔记(2)

/ 注册

全部文章 / 图论（共8篇）

codeforces 1093D 【染色求奇环+计数】

昨天晚上跟失了智一样。一直陷在一个死胡同里出不来后来发现了bug 改了一处，没有改第二处难受。 #include <bits/stdc++.h> #define cl(a) memset(a,0,sizeof(a)) #define sc(x) scanf("%d&q...

2018-12-16

0 406

codeforces 1063B. Labyrinth 【01bfs】

题目大意：在一个地图上，有些点不能走，有些点可以走，向左走向右走会有花费，向上和向下没有，现在给定起点，和向左走、向右走的最多步数，问能够走到的点有多少个题目分析：这个题如果直接bfs 去搜的话，没有办法很好的更新到达某个点最少需要多少个向左走，所以我们用bfs跑一个最短路，dist[i][j]...

2018-10-19

0 554

codeforce 964D Destruction of a Tree[dfs]

题目大意：给你一棵树，每次只能删除度为2的结点，问你能否将整棵树删除，如果可以的话，就输出路径题目分析，对于一棵树的某一个结点的子树来说，如果他的所有结点的度都是奇数，而该结点的度是偶数的话，那么其一定为一个能够先删除的结点，因为如果不先删除该结点，而先删除该结点的父结点，那么这个结点的度就会变...

dfs

2018-04-25

0 469

hdu 6026 Deleting Edges 【最短路+计数】

题目大意:给你一个图，要把它删成一棵树，并且使得0这个结点从树上到达任意结点的距离和原图中的最短路径相等分析：我们对于某一个点来说，只需要知道有多少条和到这个点最短路的路径，乘起来就可以注意个数是一个乘积的形式，应该用一种递推的方式去求； #include <bits/stdc++....

2018-04-23

0 418

HDU - 1217 Arbitrage [最短路]

题目大意，货币之间对兑换，如果起始有 1 美元，1美元=0.5英镑 1英镑=10法郎，1法郎=0.21 美元。经过交换能够得到 1*0.5*10*0.21=1.05 美元，问给定货币和汇率，能够实现上述操作分析：我们把乘法两边取对数，就变成 lg0.5+lg10+lg0.21>lg 1=...

zu

2018-03-12

0 406

CSP第十二次行车路线【80分】

问题描述　　小明和小芳出去乡村玩，小明负责开车，小芳来导航。　　小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。　　例如：有5个路口，1号路口到2号路口为小道，2号路口到...

2018-03-02

0 766

图论练习-有向图的强连通分量【tarjan】

这周刚刚看了图论的一些东西，感觉自己理解比较费劲，所以这里小小总结一下，如果有误，欢迎指出好了，现在我们来看一下图论的一些基础的概念：有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连...

2017-10-20

0 445

图论的模板

这里整理一些图论的模板最小生成树：kcruskal 算法自剩下的未选取的边中找到最小边如果和已选取的构成回路，则放弃 int kcruskal(){ int res=0; int i; sort(ed.begin,ed.end); for(i=1;i&...

2017-04-09

0 318