RainAir
My OI Blog
RainAir

强连通分量
文章归档

「NOI2017」游戏

建议大家去 UOJ 交题:链接 题目描述 有 $n$ 场游戏和三种车,每个游戏可以选择用一种车,每个游戏可能要求不能使用某种车,也可能没有要求。 给出 $m$ 个要求,表示如果第 $u$ 个游戏用了 $x$ 车,那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。 $n \leq 5 \times…

   111   2019-10-12   111 去吊打作者

2-SAT 学习笔记

定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本:每个等式中只有两个变量参与。 有 $n$ 个 $0/1$ 变量和 $m$ 个等式,每个等式形如 $x_i \text{op} x_j =k$,其中 $op$ 是一个位运算。 你要求出一组可行解。 求解 将每个 $x_i$ 拆成两…

   124   2019-10-12   124 去吊打作者

「NOIP2009」最优贸易

题目链接 题目 题目描述 $ C $ 国有 $ n $ 个大城市和 $ m $ 条道路,每条道路连接这 $ n $ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $ m $ 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也…

   319   2018-06-03   319 去吊打作者

强连通分量

概念 我们先来明确一些概念。 子图 图G=(V,E),G’=(V’,E’)中,若V’ ∈ V,E’ ∈ E,并且E’中的边所关联的顶点都在V’中,则称图G’是图G的子图 强连通性 对有向图G=(V,E)而言,若对于G中任意两个顶点Vi和Vj(Vi≠Vj ),都有一条从Vi到Vj的(有向路径),同时还有一…

   381   2018-03-17   381 去吊打作者
标签
近期评论