青烟绕指柔

图论

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

太空飞行计划

题目描述 W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为...

2019-12-27

0 816

试题库问题

题目描述假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。对于给定的组卷要求，计算满足要求的组卷方案。输入格式第1行有2个正整数k和n (2 <=k<...

2019-12-27

0 505

最小路径覆盖问题

题目求有向无环图的最小路径覆盖（可以从任意一个点开始）题目链接：洛谷P 2764 二分图性质：最小路径覆盖 == 顶点数 - 最大匹配数所以此题我们可以转化为求最大匹配来做，但是麻烦的是输出路径。考虑建图：我们可以把点拆成两个点，分别为入点和出点，让超级源点S连向每...

2019-12-27

0 387

最小路径覆盖详解

定义：通俗点讲，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。而最小路径覆盖又分为：最小不相交路径覆盖和最小可相交路径覆盖。最小不相交路径覆盖：就是我们找到的每条路径不能相交，就是每条路径不能有同一个点。最小可相交路径覆盖：这个与上面相对应，就是可以相交。 ...

2019-12-27

0 914

[USACO5.4]奶牛的电信

题目描述农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,…,a©，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a©就可以互发电邮。很不幸，有时候奶牛会不小心踩到电脑上，农夫约...

2019-12-27

0 379

分配问题

题目复制乱码，就不复制了。链接：落谷 P4014 很裸的一道二分图权值匹配，所以我们可以采用 KM 算法求解，但是我们还有一个更简单的算法，那就是费用流求解，我们建立一个超级源点S，和一个超级汇点T,让S连向人，让任务连向T，且费用都为0，流量为1. 然后根据输入的数据，对人和任务连线即可，...

2019-12-27

0 412

善意的投票

题目大意：幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的...

2019-12-27

0 425

Path - HDU6582

Problem Description Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too m...

2019-12-27

0 401

A_star 第K短路

给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。注意：每条最短路中至少要包含一条边。输入格式第一行包含两个整数N和M。接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。最后一行包含三个整...

2019-12-27

0 406

树的重心

定义及性质定义1：找到一个点,删除它得到的森林中最大的子树节点数最少（也就是最大的连通块的点数最小）,那么这个点就是这棵树的重心。定义2：删除重心后得到的所有子树，其顶点数必然不超过n/2 性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。性质...

2019-12-27

0 526