結果

問題 No.2713 Just Solitaire
ユーザー nomeaningnomeaning
提出日時 2024-03-31 15:19:30
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 2,982 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 185,012 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-31 15:19:33
合計ジャッジ時間 2,649 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 1 ms
6,676 KB
testcase_06 WA -
testcase_07 AC 1 ms
6,676 KB
testcase_08 AC 1 ms
6,676 KB
testcase_09 AC 1 ms
6,676 KB
testcase_10 AC 1 ms
6,676 KB
testcase_11 WA -
testcase_12 AC 1 ms
6,676 KB
testcase_13 WA -
testcase_14 AC 1 ms
6,676 KB
testcase_15 AC 0 ms
6,676 KB
testcase_16 AC 1 ms
6,676 KB
testcase_17 AC 1 ms
6,676 KB
testcase_18 AC 1 ms
6,676 KB
testcase_19 WA -
testcase_20 AC 1 ms
6,676 KB
testcase_21 AC 1 ms
6,676 KB
testcase_22 AC 1 ms
6,676 KB
testcase_23 AC 2 ms
6,676 KB
testcase_24 AC 2 ms
6,676 KB
testcase_25 WA -
testcase_26 AC 2 ms
6,676 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 2 ms
6,676 KB
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[derive(Clone)]
struct Edge {
    rev: usize,
    to: usize,
    cap: i64,
}

struct Graph {
    edge: Vec<Vec<Edge>>,
    visited: Vec<bool>,
}

impl Graph {
    fn new(n: usize) -> Self {
        Self {
            edge: vec![vec![]; n],
            visited: vec![false; n],
        }
    }

    fn add_edge(&mut self, src: usize, dst: usize, cap: i64) {
        let dst_len = self.edge[dst].len();
        let src_len = self.edge[src].len();
        self.edge[src].push(Edge {
            rev: dst_len,
            to: dst,
            cap,
        });
        self.edge[dst].push(Edge {
            rev: src_len,
            to: dst,
            cap: 0,
        })
    }

    fn dfs(&mut self, pos: usize, goal: usize, flow: i64) -> i64 {
        if pos == goal {
            return flow;
        }
        self.visited[pos] = true;

        for i in 0..self.edge[pos].len() {
            let e = &self.edge[pos][i];
            if e.cap == 0 || self.visited[e.to] {
                continue;
            }
            let flow = self.dfs(e.to, goal, std::cmp::min(flow, e.cap));
            let e = &mut self.edge[pos][i];
            if flow > 0 {
                e.cap -= flow;
                let e = e.clone();
                self.edge[e.to][e.rev].cap += flow;
                return flow;
            }
        }
        return 0;
    }

    fn max_flow(&mut self, src: usize, dst: usize) -> i64 {
        let mut flow = 0;
        loop {
            self.visited = vec![false; self.visited.len()];
            let f = self.dfs(src, dst, INF);
            if f == 0 {
                return flow;
            }
            flow += f;
        }
    }
}

const INF: i64 = 1_000_000_000_000_000;

fn main() {
    let stdin = std::io::stdin();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let line: Vec<&str> = line.split_whitespace().collect();
    let n = line[0].parse::<usize>().unwrap();
    let m = line[1].parse::<usize>().unwrap();

    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let a: Vec<_> = line
        .split_whitespace()
        .map(|s| s.parse::<i64>().unwrap())
        .collect();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let b: Vec<_> = line
        .split_whitespace()
        .map(|s| s.parse::<i64>().unwrap())
        .collect();
    let mut g = Graph::new(n + m + 2);
    // 0: st
    // 1: ed
    for (i, &a) in a.iter().enumerate() {
        g.add_edge(0, 2 + i, a);
    }

    for (i, &b) in b.iter().enumerate() {
        g.add_edge(2 + n + i, 1, b);
        let mut line = String::new();
        stdin.read_line(&mut line).unwrap();
        let input: Vec<_> = line
            .split_whitespace()
            .map(|s| s.parse::<usize>().unwrap())
            .collect();
        for pos in &input[1..] {
            g.add_edge(2 + pos - 1, 2 + n + i, INF);
        }
    }
    println!("{}", b.iter().sum::<i64>() - g.max_flow(0, 1));
}
0