結果

問題 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
}
0