?

# [SNOI2017]炸弹

## 题目描述

$X_i-R_i≤Xj≤X_i+R_i$ ，那么，该炸弹也会被引爆。

4
1 1
5 1
6 5
15 15

32

## 说明

$N≤500000$，
$-10^{18}≤X_i≤10^{18}$，
$0≤R_i≤2 \times 10^{18}$。

# CF1155F Delivery Oligopoly

• 这个子图必须也是边双连通分量
• 这个子图的边数最少

$( 3 \le n \le 14, n \le m \le \frac{n(n - 1)}{2} )$

## 题解

the $G$ is 2EC is quivilant to the $V \in \{V_i | V_i \in G \and V_i \notin G’\}$ , that V have at least edges connecting the two different $V’\in G’$ and $G’$ is 2EC.

proof: Assume the to different vertexes are P1 , P2 , we prove P1 -> V have two different ways.

$\because$ G’ is 2EC $\and P1 -> V \and P2 -> V$

$\therefore$ G’ + V is 2EC

So we could inductively prove that.

let $f_S$ means the least number of edges to form 2EC. $Lk1_S$