# 2023-02-14：魔物了占领若干据点，这些据点被若干条道路相连接， roads[i] = [x, y]

2023-02-14：魔物了占领若干据点，这些据点被若干条道路相连接，
roads[i] = [x, y] 表示编号 x、y 的两个据点通过一条道路连接。

``````use std::iter::repeat;
fn main() {
let cost = vec![1, 2, 3, 4, 5, 6];
vec![0, 1],
vec![0, 2],
vec![1, 3],
vec![2, 3],
vec![1, 2],
vec![2, 4],
vec![2, 5],
];
let ans = unsafe { Solution::minimum_cost(cost, roads) };
println!("ans = {:?}", ans);
}

struct Solution {}

impl Solution {
pub fn minimum_cost(cost: Vec<i32>, roads: Vec<Vec<i32>>) -> i64 {
let n = cost.len() as i32;
if n == 1 {
return cost[0] as i64;
}
let m = roads.len() as i32;
let mut dc = DoubleConnectedComponents::new(n, m, &mut roads);
let mut ans: i64 = 0;
// dcc {a,b,c} {c,d,e}
if dc.dcc.len() == 1 {
ans = i64::MAX;
for num in cost.iter() {
ans = get_min(ans, *num as i64);
}
} else {
// 不只一个点双连通分量
let mut arr: Vec<i32> = vec![];
for set in dc.dcc.iter() {
let mut cutCnt = 0;
let mut curCost = i32::MAX;
for nodes in set.iter() {
if dc.cut[*nodes as usize] {
cutCnt += 1;
} else {
curCost = get_min(curCost, cost[*nodes as usize]);
}
}
if cutCnt == 1 {
arr.push(curCost);
}
}
arr.sort_by(|a, b| a.partial_cmp(b).unwrap());
for i in 0..arr.len() as i32 - 1 {
ans += arr[i as usize] as i64;
}
}
return ans;
}
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}

struct DoubleConnectedComponents {
// 链式前向星建图
next: Vec<i32>,
to: Vec<i32>,

dfn: Vec<i32>,
low: Vec<i32>,
stack: Vec<i32>,
dcc: Vec<Vec<i32>>,
cut: Vec<bool>,
edgeCnt: i32,
dfnCnt: i32,
top: i32,
root: i32,
}
impl DoubleConnectedComponents {
pub fn new(n: i32, m: i32, roads: &mut Vec<Vec<i32>>) -> Self {
let mut ans = DoubleConnectedComponents {
next: vec![],
to: vec![],

dfn: vec![],
low: vec![],
stack: vec![],
dcc: vec![],
cut: vec![],
edgeCnt: 0,
dfnCnt: 0,
top: 0,
root: 0,
};
ans.init(n, m);
ans.creatDcc(n);
ans
}

fn init(&mut self, n: i32, m: i32) {
let t = repeat(-1).take(n as usize).collect::<Vec<i32>>();
let t = repeat(0).take((m << 1) as usize).collect::<Vec<i32>>();
self.next = t;
let t = repeat(0).take((m << 1) as usize).collect::<Vec<i32>>();
self.to = t;
let t = repeat(0).take(n as usize).collect::<Vec<i32>>();
self.dfn = t;
let t = repeat(0).take(n as usize).collect::<Vec<i32>>();
self.low = t;
let t = repeat(0).take(n as usize).collect::<Vec<i32>>();
self.stack = t;
let t = repeat(false).take(n as usize).collect::<Vec<bool>>();
self.cut = t;
self.edgeCnt = 0;
self.dfnCnt = 0;
self.top = 0;
self.root = 0;
}

fn createGraph(&mut self, roads: &mut Vec<Vec<i32>>) {
}
}

fn add(&mut self, u: i32, v: i32) {
self.to[self.edgeCnt as usize] = v;
self.next[self.edgeCnt as usize] = self.head[u as usize];
self.edgeCnt += 1;
}

fn creatDcc(&mut self, n: i32) {
for i in 0..n {
// 0 1 2 3 n-1
if self.dfn[i as usize] == 0 {
self.root = i;
self.tarjan(i);
}
}
}

fn tarjan(&mut self, x: i32) {
self.dfnCnt += 1;
self.low[x as usize] = self.dfnCnt;
self.dfn[x as usize] = self.low[x as usize];
self.stack[self.top as usize] = x;
self.top += 1;
let mut flag = 0;
if x == self.root && self.head[x as usize] == -1 {
self.dcc.push(vec![]);
let t = (self.dcc.len() as i32 - 1) as usize;
self.dcc[t].push(x);
} else {
// 当前来到的节点是x
// x {a,b,c}
let mut i = self.head[x as usize];
while i >= 0 {
// y是下级节点
let mut y = self.to[i as usize];
if self.dfn[y as usize] == 0 {
// y点没遍历过！
self.tarjan(y);
if self.low[y as usize] >= self.dfn[x as usize] {
// 正在扎口袋
flag += 1;
if x != self.root || flag > 1 {
self.cut[x as usize] = true;
}
let mut curAns: Vec<i32> = vec![];
// 从栈里一次弹出节点
// 弹到y停！
// 弹出的节点都加入集合，x也加入，x不弹出
self.top -= 1;
let mut z = self.stack[self.top as usize];
while z != y {
curAns.push(z);
self.top -= 1;
z = self.stack[self.top as usize];
}
curAns.push(y);
curAns.push(x);
self.dcc.push(curAns);
}
self.low[x as usize] = get_min(self.low[x as usize], self.low[y as usize]);
} else {
// y点已经遍历过了！
self.low[x as usize] = get_min(self.low[x as usize], self.dfn[y as usize]);
}
i = self.next[i as usize];
}
}
}
}
``````

(=￣ω￣=)··· 暂无内容！

227

11

20

6