結果

問題 No.2713 Just Solitaire
コンテスト
ユーザー nomeaning
提出日時 2024-03-31 15:19:30
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,982 bytes
コンパイル時間 11,868 ms
コンパイル使用メモリ 387,804 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-30 20:33:43
合計ジャッジ時間 13,043 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 11
権限があれば一括ダウンロードができます

ソースコード

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