题目:https://vjudge.net/contest/191379#problem/B
题目大意
给你N个爆炸点,一个爆照点可以引爆在它爆炸范围的其他爆炸点,点燃炸弹需要消耗,问你引爆所有炸弹真的最小花费。
分析
其实当时做的时候想到这个思路了,但是没有继续想下去,其实它就是一个scc的缩点的变形。
1. 首先我们可构造一个DAG,如果A可以引爆B, 那么A看作可达B。
2. 对于生成的DAG, 它有可能有环,当它有环的时候,引爆环上的任意一点造成的效果都是一致的,我们可以将这个环缩成一个点, 这里可以用tarjan去缩点染色。
3. 很容易想到,对于新的DAG来说入度为0的点是一定要引爆的,因为没有炸弹可以引爆它,那么只需要累加这些入度为0的点就行了。
代码
/******************************************************************** * File Name: B.cpp * Author: Sequin * mail: Catherine199787@outlook.com * Created Time: 二 10/24 10:21:01 2017 *************************************************************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <ctype.h>
#include <set>
#include <vector>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <climits>