「NOI2017」游戏
建议大家去 UOJ 交题：链接题目描述有 $n$ 场游戏和三种车，每个游戏可以选择用一种车，每个游戏可能要求不能使用某种车，也可能没有要求。 给出 $m$ 个要求，表示如果第 $u$ 个游戏用了 $x$ 车，那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。 $n \leq 5 \times 10^4,m \leq 10^5$，没有要求的游戏个数 $d$ 不超过 $8$。题解前置小知识...
建议大家去 UOJ 交题：链接题目描述有 $n$ 场游戏和三种车，每个游戏可以选择用一种车，每个游戏可能要求不能使用某种车，也可能没有要求。 给出 $m$ 个要求，表示如果第 $u$ 个游戏用了 $x$ 车，那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。 $n \leq 5 \times 10^4,m \leq 10^5$，没有要求的游戏个数 $d$ 不超过 $8$。题解前置小知识...
定义SAT维基百科——Boolean_satisfiability_problem2-SATSAT 的简化版本：每个等式中只有两个变量参与。 有 $n$ 个 $0/1$ 变量和 $m$ 个等式，每个等式形如 $x_i \text{op} x_j =k$，其中 $op$ 是一个位运算。 你要求出一组可行解。求解将每个 $x_i$ 拆成两个点 $x_{i,0}$ 和 $x_{i,1}$ 表示 $...
题目链接题目题目描述$ C $ 国有 $ n $ 个大城市和 $ m $ 条道路，每条道路连接这 $ n $ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $ m $ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
概念我们先来明确一些概念。子图图G=(V，E)，G’=(V’，E’)中，若V’ ∈ V，E’ ∈ E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图强连通性对有向图G=(V,E)而言，若对于G中任意两个顶点Vi和Vj（Vi≠Vj ），都有一条从Vi到Vj的（有向路径），同时还有一条从Vj到Vi的(有向)路径，则称有向图G是强连通的强连通分量（SCC）有向图强连通的 极大 子图