#979259 (Rust) No.2604 Initial Motion

• 問題: No.2604 Initial Motion
• ユーザー: 37kt
• 提出日時: 2024-05-06 09:20:04
• 言語: Rust (1.77.0)
• 結果: 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 {}
    }
}