“图论”相关日志
-
-
- 最小生成树（prim算法）100天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 求最小生成树，prim算法 long long n; //节点个数long long...
-
- 图论总结103天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 1、图的存储方式： 临接表、临接矩阵 2、BFS（特例：优先队列求解） http://magicode.blog.sohu.com/114935245.html http://magicode.blog.sohu.com/114899897.html http://magicode.blog.s...
-
- 有向图强连通分量103天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 有向图强连通分量正向DFS，算出finishTime，finishTime从大到小排序，图反向DFS简要证明：强连通分量C1到强连通分量C2有一条边则F[C1]>F[C2]图反向时（变成C2到C1有边），DFS，先遍历C1中的点，到达不了C2，所以求出来的是C1这个强连通分量。遍历C2中的点，...
-
- 二分匹配103天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 二分图最大匹配问题：1、网络流的方法，增加源点和终点，所有点边权值都为1，求出最大网络流（算法导论上有）2、匈牙利算法摘自http://hi.baidu.com/acmost/blog/item/82affc62f6fa15680d33faea.html网上找的程序（自己还没有写）#define N...
-
- USACO Overfencing 广搜112天前
- 作者：Sasuke★ACM Space 标签：
广度优先
图论
- 【题目大意】：给了一张图，图上有两个出口，求从迷宫中任意一点走到出口所需要的最短时间。 ----------------------------------------------------------【分析】：迷宫中的每个点到出口都可能有不同的时间，求的是至少需要的时候，所以先取从一个点到出口的...
-
- 差分约束系统115天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 差分约束系统：通过约束条件，列出不等式建图，增加一个源点，求出源点到终点的最短（或最长）路径由于差分约束系统存在负权值的边，所以得用Bellman-Ford或SPFA求源点到终点的距离在差分约束系统求最大值时，要建图求最短路径，不等式采用小于等于号（<=）,即用求源点到终点的最小距离的方法，求...
-
- 欧拉回路116天前
- 作者：Coding Now,Programming Future …… 标签：
图论
Shirley
- 1、无向图：欧拉回路：所有点的度数为偶数欧拉路径：（起点和终点不一致的情况下）有两个点的度为奇数（这两个点分别为起点和终点），其它点度数均为偶数但要先判断是否为连通图（可以用并查集、bfs、dfs判断）2、有向图：欧拉回路：所有点的入度等于出度欧拉路径：有一个点的入度比出度大1，有一个点的出度比入度...