Absoler

图论

Java开发(1) MFC(1) 动态规划(5) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

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

NC14254 Color（Vizing定理）来自专栏

题目链接 https://ac.nowcoder.com/acm/problem/14254 题目大意：给一个二分图（n<=1e3，m<=2e3），要求对它的边进行染色，相邻边（即有公共点的边）不能是同一种颜色，问最少用多少种颜色（k）能完成染色任务，并输出一组可行解（每条边的颜色为1...

每日一题二分图 Color

2020-07-09

2 1279

强连通分量分解

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。实现算法：两次dfs，第一次 dfs 遍历将顶点后序(pos...

2020-05-09

0 559

SPFA算法简介

SPFA为Shortest Path Faster Algorithm的缩写，用来解决单源最短路问题，在效率上相比传统算法有一定优势。算法首先需要获取点点距离，不相通的点间距设为inf，准备一个vis数组用来判断点是否在队列中，一个dis数组记录每个点到起点的最短距离。算法核心：不断...

2020-05-09

0 744

最小生成树poj2253

样题：poj2253 题目链接题目大意：一只青蛙需从1号石头经由一系列石头跳跃至2号石头，每块石头相隔一定距离（任意两石头均可跳），求出在所有可能的跳跃路径中，单步跳跃距离最大值最小的一条路径中，该值的大小。向最小生成树算法方向分析，无论是prim还是kruskal算法，均是优先挑选短...

2020-05-09

0 382

最小路径覆盖（匈牙利算法）

最小路径算法解决以下问题：对于一个DAG，找到最少的路径（连续的若干边）条数（单个顶点也算一条路径），覆盖所有顶点。按路径可否相交分为两类。首先是路径不相交的最小覆盖：我们可以把每个顶点拆为出点和入点，这时每种路径安排都是一个二分图P'，问题转化为了求该二分图的最大匹配：如果在P'中增加一条...

2020-05-09

0 1160

树上启发式合并（dsu on tree）一篇就会！理解其他博客的基础

这个算法真是研究了好久才明白……众多博客真的不是面向小白的模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。首先想...

2020-05-09

0 525

上下界网络流 cf704D

cf704D 给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点缺少...

2020-05-09

0 437