結果

問題 No.3201 Corporate Synergy
ユーザー Moss_Local
提出日時 2025-07-11 22:20:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,643 bytes
コンパイル時間 23,856 ms
コンパイル使用メモリ 380,812 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 22:21:06
合計ジャッジ時間 23,179 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
   --> src/main.rs:119:9
    |
119 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:125:9
    |
125 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:130:9
    |
130 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:136:9
    |
136 |     let mut vec: Vec<f64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:141:9
    |
141 |     let mut vec: Vec<char> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:146:9
    |
146 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:267:9
    |
267 |     let mut pi: Vec<i64> = read_vec();
    |         ----^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:280:13
    |
280 |         let mut vec: Vec<i64> = read_vec();
    |             ----^^^
    |             |
    |             help: remove this `mut`

warning: variable `INF` should have a snake case name
   --> src/main.rs:232:21
    |
232 |                 let INF = 2_000_000_001;
    |                     ^^^ help: convert the identifier to snake case: `inf`
    |
    = note: `#[warn(non_snake_case)]` on by default

ソースコード

diff #

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
// use core::num;
use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::io::BufRead;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
// const MOD: i64 = MOD2;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;

// use proconio::input;
// const MOD: i64 = INF;

use cmp::Ordering::*;
use std::collections::*;

use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        //if expr
        println!("{}", $x);
    };
}

macro_rules! vp {
    // vector print separate with space
    ($x:expr) => {
        println!(
            "{}",
            $x.iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    };
}

macro_rules! d {
    ($x:expr) => {
        eprintln!("{:?}", $x);
    };
}
macro_rules! yn {
    ($val:expr) => {
        if $val {
            println!("Yes");
        } else {
            println!("No");
        }
    };
}

macro_rules! map{
    // declear btreemap
    ($($key:expr => $val:expr),*) => {
        {
            let mut map = ::std::collections::BTreeMap::new();
            $(
                map.insert($key, $val);
            )*
            map
        }
    };
}

macro_rules! set{
    // declear btreemap
    ($($key:expr),*) => {
        {
            let mut set = ::std::collections::BTreeSet::new();
            $(
                set.insert($key);
            )*
            set
        }
    };
}

//input output
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut vec: Vec<f64> = read_vec();
    (vec[0], vec[1])
}

fn readcc() -> (char, char) {
    let mut vec: Vec<char> = read_vec();
    (vec[0], vec[1])
}

fn readuuu() -> (usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2])
}

pub mod dinic {
    #[derive(Clone, Copy, Debug)]
    struct Edge {
        to: usize,
        cap: i64,
        rev: usize,
    }
    pub struct Network {
        g: Vec<Vec<Edge>>,
        level: Vec<Option<usize>>,
        iter: Vec<usize>,
    }
    #[doc = "direct flow graph. O(EV^2)"]
    impl Network {
        pub fn new(n: usize) -> Network {
            Network {
                g: vec![vec![]; n],
                level: vec![None; n],
                iter: vec![0; n],
            }
        }
        pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
            assert!(cap >= 0);

            let from_rev = self.g[to].len();
            let to_rev = self.g[from].len();
            self.g[from].push(Edge {
                to: to,
                cap: cap,
                rev: from_rev,
            });
            self.g[to].push(Edge {
                to: from,
                cap: 0,
                rev: to_rev,
            });
        }
        fn n(&self) -> usize {
            self.g.len()
        }
        fn bfs(&mut self, s: usize) {
            self.level = vec![None; self.n()];
            let mut q = std::collections::VecDeque::new();
            q.push_back(s);
            self.level[s] = Some(0);
            while let Some(v) = q.pop_front() {
                for e in &self.g[v] {
                    if e.cap > 0 && self.level[e.to].is_none() {
                        self.level[e.to] = self.level[v].map(|x| x + 1);
                        q.push_back(e.to);
                    }
                }
            }
        }
        fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
            if v == t {
                return f;
            }
            let iter_v_cur = self.iter[v];
            for i in iter_v_cur..self.g[v].len() {
                let e = self.g[v][i].clone();
                if e.cap > 0 && self.level[v] < self.level[e.to] {
                    let d = self.dfs(e.to, t, std::cmp::min(f, e.cap));
                    if d > 0 {
                        self.g[v][i].cap -= d;
                        self.g[e.to][e.rev].cap += d;
                        return d;
                    }
                }
                self.iter[v] += 1;
            }
            return 0;
        }
        pub fn max_flow(&mut self, s: usize, t: usize) -> i64 {
            let mut flow = 0;
            loop {
                self.bfs(s);
                // finally if we could not find any path to t then return flow
                if self.level[t].is_none() {
                    return flow;
                }

                let INF = 2_000_000_001;
                self.iter = vec![0; self.n()];
                let mut f = self.dfs(s, t, INF);
                while f > 0 {
                    flow += f;
                    f = self.dfs(s, t, INF);
                }
            }
        }
    }
}
// #[test]
// fn test_dinic() {
//     use dinic::*;
//     let mut nw = Network::new(5);

//     let conns = [
//         (0, 1, 10),
//         (0, 2, 2),
//         (1, 2, 6),
//         (1, 3, 6),
//         (3, 2, 3),
//         (2, 4, 5),
//         (3, 4, 8),
//     ];

//     for conn in &conns {
//         nw.add_edge(conn.0, conn.1, conn.2);
//     }

//     assert_eq!(nw.max_flow(0, 4), 11);
// }
fn main() {
    let n: usize = read();
    let mut p = vec![0i64; n + 1];
    let mut pi: Vec<i64> = read_vec();
    for i in 1..=n {
        p[i] = pi[i - 1] as i64; // Assuming pi is a vector of usize
    }
    let m: usize = read();
    let mut deps = Vec::with_capacity(m);
    for _ in 0..m {
        let (u, v) = readuu();
        deps.push((u, v));
    }
    let k: usize = read();
    let mut syn = Vec::with_capacity(k);
    for _ in 0..k {
        let mut vec: Vec<i64> = read_vec();
        let a: usize = vec[0] as usize;
        let b: usize = vec[1] as usize;
        let s: i64 = vec[2];
        syn.push((a, b, s));
    }
    let s = 0;
    let t = n + k + 1;
    let mut mf = dinic::Network::new(t + 1);
    let mut sum = 0i64;
    for i in 1..=n {
        if p[i] > 0 {
            mf.add_edge(s, i, p[i]);
            sum += p[i];
        } else if p[i] < 0 {
            mf.add_edge(i, t, -p[i]);
        }
    }
    for (u, v) in deps {
        mf.add_edge(v, u, INF);
    }
    for j in 0..k {
        let node = n + 1 + j;
        let (a, b, w) = syn[j];
        mf.add_edge(s, node, w);
        sum += w;
        mf.add_edge(node, a, INF);
        mf.add_edge(node, b, INF);
    }
    let flow = mf.max_flow(s, t);
    let ans = sum - flow;
    p!(ans);
}
0