結果
| 問題 |
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 |
| コンパイル時間 | 13,395 ms |
| コンパイル使用メモリ | 398,384 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-09-19 23:40:51 |
| 合計ジャッジ時間 | 14,139 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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
ソースコード
// -*- 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);
}