結果

問題 No.177 制作進行の宮森あおいです！
ユーザー 草苺奶昔
提出日時 2023-03-14 18:58:19
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,465 bytes
コンパイル時間 12,292 ms
コンパイル使用メモリ 231,096 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 08:21:47
合計ジャッジ時間 13,021 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "os"
)
func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var w int
    fmt.Fscan(in, &w)
    var n int
    fmt.Fscan(in, &n)
    A := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &A[i])
    }
    var m int
    fmt.Fscan(in, &m)
    B := make([]int, m)
    for i := 0; i < m; i++ {
        fmt.Fscan(in, &B[i])
    }
    ok := make([][]bool, m)
    for i := 0; i < m; i++ {
        ok[i] = make([]bool, n)
        for j := 0; j < n; j++ {
            ok[i][j] = true
        }
    }
    for i := 0; i < m; i++ {
        var q int
        fmt.Fscan(in, &q)
        for j := 0; j < q; j++ {
            var x int
            fmt.Fscan(in, &x)
            ok[i][x-1] = false
        }
    }
    res := 制作進行の宮森あおいです(w, A, B, ok)
    if res {
        fmt.Fprintln(out, "SHIROBAKO")
    } else {
        fmt.Fprintln(out, "BANSAKUTSUKITA")
    }
}
func 制作進行の宮森あおいです(w int, A, B []int, ok [][]bool) bool {
    n, m := len(A), len(B)
    S, T := n+m, n+m+1
    flow := NewDinic(n + m + 2)
    left := func(i int) int { return i }
    right := func(i int) int { return i + n }
    for i := 0; i < n; i++ {
        flow.AddEdge(S, left(i), A[i])
    }
    for i := 0; i < m; i++ {
        flow.AddEdge(right(i), T, B[i])
    }
    for j := 0; j < m; j++ {
        for i := 0; i < n; i++ {
            if ok[j][i] {
                flow.AddEdge(left(i), right(j), INF)
            }
        }
    }
    return flow.MaxFlow(S, T) >= w
}
const INF int = 1e18
type DinicEdge struct {
    to    int
    cap   int // 剩余容量
    rev   int // 逆向边在 G[to] 中的序号
    isRev bool
    index int
}
type Dinic struct {
    graph   [][]DinicEdge
    minCost []int
    iter    []int
}
func NewDinic(n int) *Dinic {
    return &Dinic{
        graph: make([][]DinicEdge, n),
    }
}
func (d *Dinic) AddEdge(from, to, cap int) {
    d.AddEdgeWithIndex(from, to, cap, -1)
}
func (d *Dinic) AddEdgeWithIndex(from, to, cap, index int) {
    d.graph[from] = append(d.graph[from], DinicEdge{to, cap, len(d.graph[to]), false, index})
    d.graph[to] = append(d.graph[to], DinicEdge{from, 0, len(d.graph[from]) - 1, true, index})
}
func (d *Dinic) MaxFlow(s, t int) int {
    flow := 0
    for d.buildAugmentingPath(s, t) {
        d.iter = make([]int, len(d.graph))
        f := 0
        for {
            f = d.findMinDistAugmentPath(s, t, INF)
            if f == 0 {
                break
            }
            flow += f
        }
    }
    return flow
}
// (from,to,流量,容量)
func (d *Dinic) GetEdges() [][4]int {
    res := make([][4]int, 0)
    for i, edges := range d.graph {
        for _, e := range edges {
            if e.isRev {
                continue
            }
            revEdge := d.graph[e.to][e.rev]
            res = append(res, [4]int{i, e.to, revEdge.cap, e.cap + revEdge.cap})
        }
    }
    return res
}
func (d *Dinic) findMinDistAugmentPath(idx, t, flow int) int {
    if idx == t {
        return flow
    }
    i := d.iter[idx]
    for i < len(d.graph[idx]) {
        e := d.graph[idx][i]
        if e.cap > 0 && d.minCost[idx] < d.minCost[e.to] {
            f := d.findMinDistAugmentPath(e.to, t, min(flow, e.cap))
            if f > 0 {
                d.graph[idx][i].cap -= f
                d.graph[e.to][e.rev].cap += f
                return f
            }
        }
        i++
        d.iter[idx]++
    }
    return 0
}
func (d *Dinic) buildAugmentingPath(s, t int) bool {
    d.minCost = make([]int, len(d.graph))
    for i := range d.minCost {
        d.minCost[i] = -1
    }
    d.minCost[s] = 0
    queue := []int{s}
    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]
        for _, e := range d.graph[v] {
            if e.cap > 0 && d.minCost[e.to] == -1 {
                d.minCost[e.to] = d.minCost[v] + 1
                queue = append(queue, e.to)
            }
        }
    }
    return d.minCost[t] != -1
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0