結果
問題 | No.2604 Initial Motion |
ユーザー | 37kt |
提出日時 | 2024-05-06 09:20:04 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 454 ms / 3,000 ms |
コード長 | 7,708 bytes |
コンパイル時間 | 13,814 ms |
コンパイル使用メモリ | 377,268 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-06 09:20:28 |
合計ジャッジ時間 | 23,768 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 11 ms
5,376 KB |
testcase_04 | AC | 10 ms
5,376 KB |
testcase_05 | AC | 10 ms
5,376 KB |
testcase_06 | AC | 11 ms
5,376 KB |
testcase_07 | AC | 10 ms
5,376 KB |
testcase_08 | AC | 11 ms
5,376 KB |
testcase_09 | AC | 10 ms
5,376 KB |
testcase_10 | AC | 11 ms
5,376 KB |
testcase_11 | AC | 11 ms
5,376 KB |
testcase_12 | AC | 11 ms
5,376 KB |
testcase_13 | AC | 340 ms
5,376 KB |
testcase_14 | AC | 281 ms
5,376 KB |
testcase_15 | AC | 114 ms
5,376 KB |
testcase_16 | AC | 322 ms
5,376 KB |
testcase_17 | AC | 374 ms
5,376 KB |
testcase_18 | AC | 357 ms
5,376 KB |
testcase_19 | AC | 360 ms
5,376 KB |
testcase_20 | AC | 321 ms
5,376 KB |
testcase_21 | AC | 290 ms
5,376 KB |
testcase_22 | AC | 356 ms
5,376 KB |
testcase_23 | AC | 304 ms
5,376 KB |
testcase_24 | AC | 334 ms
5,376 KB |
testcase_25 | AC | 436 ms
5,376 KB |
testcase_26 | AC | 312 ms
5,376 KB |
testcase_27 | AC | 262 ms
5,376 KB |
testcase_28 | AC | 297 ms
5,376 KB |
testcase_29 | AC | 330 ms
5,376 KB |
testcase_30 | AC | 276 ms
5,376 KB |
testcase_31 | AC | 314 ms
5,376 KB |
testcase_32 | AC | 369 ms
5,376 KB |
testcase_33 | AC | 194 ms
5,376 KB |
testcase_34 | AC | 226 ms
5,376 KB |
testcase_35 | AC | 425 ms
5,376 KB |
testcase_36 | AC | 454 ms
5,376 KB |
testcase_37 | AC | 136 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 1 ms
5,376 KB |
testcase_40 | AC | 300 ms
5,376 KB |
testcase_41 | AC | 305 ms
5,376 KB |
コンパイルメッセージ
warning: unused variable: `vs` --> src/main.rs:19:13 | 19 | let mut vs = mcf.add_vertices(n); | ^^ help: if this is intentional, prefix it with an underscore: `_vs` | = note: `#[warn(unused_variables)]` on by default warning: variable does not need to be mutable --> src/main.rs:19:9 | 19 | let mut vs = mcf.add_vertices(n); | ----^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
pub use __cargo_equip::prelude::*; use min_cost_b_flow::MinCostBFlow; #[allow(unused_imports)] use proconio::{ input, marker::{Bytes, Chars, Usize1}, }; fn main() { input! { k: usize, n: usize, m: usize, a: [Usize1; k], b: [i64; n], } let mut mcf = MinCostBFlow::new(); let mut vs = mcf.add_vertices(n); let s = mcf.add_vertex(); let t = mcf.add_vertex(); for &x in &a { mcf.add_edge(s, x, 0, 1, 0); } for i in 0..n { mcf.add_edge(i, t, 0, b[i], 0); } for _ in 0..m { input! { u: Usize1, v: Usize1, d: i64, } mcf.add_edge(u, v, 0, 2000, d); mcf.add_edge(v, u, 0, 2000, d); } let res = mcf.min_cost_flow(s, t).unwrap().0; println!("{}", res); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `min-cost-b-flow 0.1.0 (path+██████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::min_cost_b_flow` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod min_cost_b_flow {use std::{cmp::Reverse,collections::BinaryHeap};const UNREACHABLE:i64=std::i64::MAX;const SCALING_FACTOR:i64=2;#[derive(Debug,Clone,Copy)]pub struct Edge{pub from:usize,pub to:usize,pub lower:i64,pub upper:i64,pub cost:i64,pub gain:i64,pub flow:i64,}pub struct MinCostBFlow{n:usize,edges:Vec<Edge_>,head:Vec<usize>,next:Vec<usize>,b:Vec<i64>,farthest:i64,potential:Vec<i64>,dist:Vec<i64>,parent:Vec<usize>,pq:BinaryHeap<Reverse<(i64,usize)>>,excess_vs:Vec<usize>,deficit_vs:Vec<usize>,}impl MinCostBFlow{pub fn new()->Self{Self{n:0,edges:vec![],head:vec![],next:vec![],b:vec![],farthest:0,potential:vec![],dist:vec![],parent:vec![],pq:Default::default(),excess_vs:vec![],deficit_vs:vec![],}}pub fn add_vertex(&mut self)->usize{self.n+=1;self.head.push(!0);self.b.push(0);self.n-1}pub fn add_vertices(&mut self,size:usize)->Vec<usize>{self.n+=size;self.head.append(&mut vec![!0;size]);self.b.append(&mut vec![0;size]);(self.n-size..self.n).collect()}pub fn add_edge(&mut self,from:usize,to:usize,lower:i64,upper:i64,cost:i64)->usize{assert!(lower<=upper);assert!(from<self.n);assert!(to<self.n);let m=self.edges.len();self.next.push(self.head[from]);self.head[from]=m;self.next.push(self.head[to]);self.head[to]=m+1;self.edges.push(Edge_{to,cap:upper,cost,flow:0,});self.edges.push(Edge_{to:from,cap:-lower,cost:-cost,flow:0,});m/2}pub fn add_supply(&mut self,v:usize,amount:i64){self.b[v]+=amount;}pub fn add_demand(&mut self,v:usize,amount:i64){self.b[v]-=amount;}pub fn get_edge(&self,e:usize)->Edge{assert!(e<=self.edges.len()/2);let e=e*2;Edge{from:self.from(e),to:self.to(e),lower:self.lower(e),upper:self.upper(e),cost:self.cost(e),gain:self.gain(e),flow:self.flow(e),}}pub fn get_edges(&self)->Vec<Edge>{(0..self.edges.len()/2).map(|e|self.get_edge(e)).collect()}pub fn min_cost_b_flow(&mut self)->Result<i64,i64>{self.potential.resize(self.n,0);for u in 0..self.n{let mut e=self.head[u];while e!=!0{let rcap=self.residual_cap(e);if rcap<0{self.push(e,rcap);self.b[u]-=rcap;let v=self.to(e);self.b[v]+=rcap;}e=self.next[e];}}let mut inf_flow=1;for e in 0..self.edges.len(){inf_flow=inf_flow.max(self.residual_cap(e));}let mut delta=1;while delta*SCALING_FACTOR<=inf_flow{delta*=SCALING_FACTOR;}while delta>0{self.saturate_negative(delta);while self.dual(delta){self.primal(delta);}delta/=SCALING_FACTOR;}let mut value=0;for Edge_{flow,cost,..}in&self.edges{value+=flow*cost;}value/=2;if self.excess_vs.is_empty()&&self.deficit_vs.is_empty(){Ok(value)}else{Err(value)}}pub fn min_cost_flow(&mut self,s:usize,t:usize)->Result<(i64,i64),(i64,i64)>{assert!(s!=t);let mut inf_flow=self.b[s].abs();let mut e=self.head[s];while e!=!0{inf_flow+=0.max(self.edges[e].cap);e=self.next[e];}self.add_edge(t,s,0,inf_flow,0);if let Err(circulation_value)=self.min_cost_b_flow(){self.head[s]=self.next[s];self.head[t]=self.next[t];self.edges.pop();self.edges.pop();return Err((circulation_value,0));}let mut inf_flow=self.b[s].abs();let mut e=self.head[s];while e!=!0{inf_flow+=self.residual_cap(e);e=self.next[e];}self.b[s]+=inf_flow;self.b[t]-=inf_flow;let mf_value=match self.min_cost_b_flow(){Ok(v)=>v,Err(v)=>v,};self.b[s]-=inf_flow;self.b[t]+=inf_flow;self.head[s]=self.next[s];self.head[t]=self.next[t];self.edges.pop();self.edges.pop();Ok((mf_value,self.b[t]))}pub fn get_result_value_i128(&mut self)->i128{let mut value=0;for e in&self.edges{value+=e.flow as i128*e.cost as i128;}value/2}pub fn get_potential(&mut self)->Vec<i64>{self.potential=vec![0;self.n];for _ in 0..self.n{for e in 0..self.edges.len(){if self.residual_cap(e)>0{let to=self.to(e);self.potential[to]=self.potential[to].min(self.potential[self.from(e)]+self.cost(e));}}}self.potential.clone()}fn from(&self,e:usize)->usize{self.edges[e^1].to}fn to(&self,e:usize)->usize{self.edges[e].to}fn flow(&self,e:usize)->i64{self.edges[e].flow}fn lower(&self,e:usize)->i64{-self.edges[e^1].cap}fn upper(&self,e:usize)->i64{self.edges[e].cap}fn cost(&self,e:usize)->i64{self.edges[e].cost}fn gain(&self,e:usize)->i64{-self.edges[e].cost}fn push(&mut self,e:usize,amount:i64){self.edges[e].flow+=amount;self.edges[e^1].flow-=amount;}fn residual_cost(&self,e:usize)->i64{self.cost(e)+self.potential[self.from(e)]-self.potential[self.to(e)]}fn residual_cap(&self,e:usize)->i64{self.edges[e].cap-self.edges[e].flow}fn dual(&mut self,delta:i64)->bool{self.dist=vec![UNREACHABLE;self.n];self.parent=vec![!0;self.n];for i in(0..self.excess_vs.len()).rev(){if self.b[self.excess_vs[i]]<delta{self.excess_vs.swap_remove(i);}}for i in(0..self.deficit_vs.len()).rev(){if self.b[self.deficit_vs[i]]>-delta{self.deficit_vs.swap_remove(i);}}for&v in&self.excess_vs{self.dist[v]=0;self.pq.push(Reverse((0,v)));}self.farthest=0;let mut deficit_count=0;while let Some(Reverse((d,u)))=self.pq.pop(){if self.dist[u]<d{continue;}self.farthest=d;if self.b[u]<=-delta{deficit_count+=1;}if deficit_count>=self.deficit_vs.len(){break;}let mut e=self.head[u];while e!=!0{if self.residual_cap(e)>=delta{let v=self.to(e);let new_dist=d+self.residual_cost(e);if self.dist[v]>new_dist{self.dist[v]=new_dist;self.pq.push(Reverse((new_dist,v)));self.parent[v]=e;}}e=self.next[e];}}self.pq.clear();for v in 0..self.n{self.potential[v]+=self.dist[v].min(self.farthest);}deficit_count>0}fn primal(&mut self,delta:i64){for i in 0..self.deficit_vs.len(){let t=self.deficit_vs[i];if self.dist[t]>self.farthest{continue;}let mut f=-self.b[t];let mut v=t;while self.parent[v]!=!0&&f>=delta{f=f.min(self.residual_cap(self.parent[v]));v=self.from(self.parent[v]);}f=f.min(self.b[v]);if f<delta{continue;}v=t;while self.parent[v]!=!0{self.push(self.parent[v],f);let u=self.from(self.parent[v]);self.parent[v]=!0;v=u;}self.b[t]+=f;self.b[v]-=f;}}fn saturate_negative(&mut self,delta:i64){self.excess_vs.clear();self.deficit_vs.clear();for u in 0..self.n{let mut e=self.head[u];while e!=!0{let rcap=self.residual_cap(e);let rcost=self.residual_cost(e);if rcost<0&&rcap>=delta{self.push(e,rcap);self.b[u]-=rcap;let v=self.to(e);self.b[v]+=rcap;}e=self.next[e];}}for v in 0..self.n{if self.b[v]>0{self.excess_vs.push(v);}else if self.b[v]<0{self.deficit_vs.push(v);}}}}struct Edge_{to:usize,cap:i64,cost:i64,flow:i64,}} } pub(crate) mod macros { pub mod min_cost_b_flow {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod min_cost_b_flow {} } }