結果
問題 | No.957 植林 |
ユーザー | 草苺奶昔 |
提出日時 | 2024-09-09 00:36:33 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 675 ms / 2,000 ms |
コード長 | 13,360 bytes |
コンパイル時間 | 15,188 ms |
コンパイル使用メモリ | 242,668 KB |
実行使用メモリ | 20,688 KB |
最終ジャッジ日時 | 2024-09-09 00:37:02 |
合計ジャッジ時間 | 28,407 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 78 ms
18,580 KB |
testcase_04 | AC | 72 ms
16,456 KB |
testcase_05 | AC | 79 ms
18,584 KB |
testcase_06 | AC | 80 ms
18,652 KB |
testcase_07 | AC | 77 ms
18,520 KB |
testcase_08 | AC | 73 ms
18,556 KB |
testcase_09 | AC | 72 ms
18,580 KB |
testcase_10 | AC | 74 ms
18,596 KB |
testcase_11 | AC | 72 ms
18,584 KB |
testcase_12 | AC | 73 ms
18,556 KB |
testcase_13 | AC | 66 ms
14,328 KB |
testcase_14 | AC | 77 ms
18,616 KB |
testcase_15 | AC | 70 ms
18,592 KB |
testcase_16 | AC | 61 ms
14,340 KB |
testcase_17 | AC | 63 ms
16,488 KB |
testcase_18 | AC | 286 ms
18,540 KB |
testcase_19 | AC | 315 ms
18,608 KB |
testcase_20 | AC | 291 ms
18,572 KB |
testcase_21 | AC | 342 ms
18,656 KB |
testcase_22 | AC | 431 ms
18,600 KB |
testcase_23 | AC | 373 ms
18,604 KB |
testcase_24 | AC | 475 ms
18,568 KB |
testcase_25 | AC | 331 ms
18,576 KB |
testcase_26 | AC | 438 ms
18,572 KB |
testcase_27 | AC | 338 ms
18,564 KB |
testcase_28 | AC | 361 ms
18,568 KB |
testcase_29 | AC | 675 ms
18,580 KB |
testcase_30 | AC | 361 ms
18,580 KB |
testcase_31 | AC | 281 ms
18,552 KB |
testcase_32 | AC | 288 ms
18,604 KB |
testcase_33 | AC | 397 ms
18,588 KB |
testcase_34 | AC | 265 ms
18,652 KB |
testcase_35 | AC | 279 ms
18,656 KB |
testcase_36 | AC | 319 ms
18,640 KB |
testcase_37 | AC | 306 ms
18,580 KB |
testcase_38 | AC | 357 ms
20,688 KB |
testcase_39 | AC | 436 ms
18,564 KB |
testcase_40 | AC | 527 ms
18,584 KB |
testcase_41 | AC | 29 ms
6,944 KB |
testcase_42 | AC | 31 ms
6,940 KB |
testcase_43 | AC | 76 ms
18,524 KB |
testcase_44 | AC | 78 ms
18,504 KB |
testcase_45 | AC | 2 ms
6,940 KB |
testcase_46 | AC | 2 ms
6,944 KB |
testcase_47 | AC | 1 ms
6,940 KB |
ソースコード
// BinaryOptimization 模型(二元集合划分问题) // 队伍划分/分组,使得某个值最大/最小 // 燃やす埋める問題, Project Selection Problem package main import ( "bufio" "fmt" "os" ) func main() { yuki_957() // yuki_1541() // yuki_2320() // abc193f() // abc259g() } // No.957 植林(消消乐) // https://yukicoder.me/problems/no/957 // 二维矩阵,选择每个格子需要花费cost[i][j] // 同时选择每个行,获得R[i]分,选择每个列,获得C[j]分. // 最大化总分-花费. // H,W<=300 func yuki_957() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var row, col int32 fmt.Fscan(in, &row, &col) cost := make([][]int, row) for i := int32(0); i < row; i++ { cost[i] = make([]int, col) for j := int32(0); j < col; j++ { fmt.Fscan(in, &cost[i][j]) } } rowScore := make([]int, row) for i := int32(0); i < row; i++ { fmt.Fscan(in, &rowScore[i]) } colScore := make([]int, col) for i := int32(0); i < col; i++ { fmt.Fscan(in, &colScore[i]) } // 左边:选,右边:不选 B := NewBinaryOptimization(row+col, false) for i := int32(0); i < row; i++ { for j := int32(0); j < col; j++ { v := cost[i][j] B.Add2(i, row+j, -v, -v, -v, 0) } } for i := int32(0); i < row; i++ { B.Add1(i, rowScore[i], 0) } for i := int32(0); i < col; i++ { B.Add1(row+i, colScore[i], 0) } res, _ := B.Calc() fmt.Fprintln(out, res) } // https://yukicoder.me/problems/no/1541 // 期末考试 // 有n个考试科目,每学一个科目就能多拿base分 // 对于每个科目i,可以花费cost来学习,学习之后有额外的收益: // 对于科目subjects[j],如果i和subjects[j]都学习了,那么就能多拿到bonus[j]分 // !最大化(总分-花费) // n<=100 // !每个科目学习还是不学习 => 燃やす埋める // 先学习所有科目,然后再割掉不学每个科目的代价(最小割<=>最小代价的划分方案) func yuki_1541() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int32 var base int fmt.Fscan(in, &n, &base) costs := make([]int, n) subjects := make([][]int32, n) bonuses := make([][]int, n) for i := int32(0); i < n; i++ { var k, cost int fmt.Fscan(in, &k, &cost) costs[i] = cost subjects[i] = make([]int32, k) bonuses[i] = make([]int, k) for j := 0; j < k; j++ { fmt.Fscan(in, &subjects[i][j]) subjects[i][j]-- } for j := 0; j < k; j++ { fmt.Fscan(in, &bonuses[i][j]) } } B := NewBinaryOptimization(n, false) for i := int32(0); i < n; i++ { B.Add1(i, 0, base-costs[i]) for j := 0; j < len(subjects[i]); j++ { B.Add2(i, subjects[i][j], 0, 0, 0, bonuses[i][j]) } } res, _ := B.Calc() fmt.Fprintln(out, res) } // No.2320 Game World for PvP // https://yukicoder.me/problems/no/2320 // 一共有n个人正在进行拔河比赛. // A数组表示现在红队的人,B数组表示现在蓝队的人. // 剩下的人加入红队或者蓝队都可以. // C[i][j] 表示i和j一起在一队的收益. // 最大化总收益. func yuki_2320() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var N, S, T int32 fmt.Fscan(in, &N, &S, &T) A := make([]int, S) B := make([]int, T) for i := int32(0); i < S; i++ { fmt.Fscan(in, &A[i]) A[i]-- } for i := int32(0); i < T; i++ { fmt.Fscan(in, &B[i]) B[i]-- } C := make([][]int, N) for i := int32(0); i < N; i++ { C[i] = make([]int, N) for j := int32(0); j < N; j++ { fmt.Fscan(in, &C[i][j]) } } belong := make([]int8, N) for i := int32(0); i < N; i++ { belong[i] = -1 } for _, v := range A { belong[v] = 0 } for _, v := range B { belong[v] = 1 } M := NewBinaryOptimization(N, false) for i := int32(0); i < N; i++ { if belong[i] == 0 { M.Add1(i, 0, -INF) } if belong[i] == 1 { M.Add1(i, -INF, 0) } } for i := int32(0); i < N; i++ { for j := i + 1; j < N; j++ { v := C[i][j] M.Add2(i, j, v, 0, 0, v) } } res, _ := M.Calc() fmt.Fprintln(out, res) } // F - Zebraness // https://atcoder.jp/contests/abc193/tasks/abc193_f // 给定一个n*n的矩阵,每个位置有一个值. // B表示黑色,W表示白色,?表示未知. // !现在要求填充所有的?为B或者W,最大化相邻位置颜色不同的数量. // n<=100. // https://kanpurin.hatenablog.com/entry/2021/02/27/225330 func abc193f() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int32 fmt.Fscan(in, &n) grid := make([]string, n) for i := int32(0); i < n; i++ { fmt.Fscan(in, &grid[i]) } B := NewBinaryOptimization(n*n, false) idx := func(i, j int32) int32 { return i*n + j } for i := int32(0); i < n; i++ { for j := int32(0); j < n; j++ { f := (i + j) & 1 h := idx(i, j) if grid[i][j] == 'W' && f == 0 { B.Add1(h, 0, -INF) } if grid[i][j] == 'W' && f == 1 { B.Add1(h, -INF, 0) } if grid[i][j] == 'B' && f == 0 { B.Add1(h, -INF, 0) } if grid[i][j] == 'B' && f == 1 { B.Add1(h, 0, -INF) } } } dir2 := [][2]int32{{1, 0}, {0, 1}} for i := int32(0); i < n; i++ { for j := int32(0); j < n; j++ { for _, d := range dir2 { ni, nj := i+d[0], j+d[1] if ni < 0 || ni >= n || nj < 0 || nj >= n { continue } h := idx(i, j) nh := idx(ni, nj) B.Add2(h, nh, 1, 0, 0, 1) } } } res, _ := B.Calc() fmt.Fprintln(out, res) } // G - Grid Card Game // https://atcoder.jp/contests/abc259/tasks/abc259_g // 给定一个矩阵Anxn (1≤ n ≤ 100),选择一些行列,可以得到这些行列包含的位置的并的数值和。 // 此外要求任意选中的行列交点处不能是负数。 // !求选择的最大值 // !时间复杂度O(V^2E) func abc259g() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var ROW, COL int32 fmt.Fscan(in, &ROW, &COL) grid := make([][]int, ROW) for i := int32(0); i < ROW; i++ { grid[i] = make([]int, COL) for j := int32(0); j < COL; j++ { fmt.Fscan(in, &grid[i][j]) } } const big int = 1 << 45 bm := NewBinaryOptimization(ROW+COL, true) rowId := func(r int32) int32 { return r } colId := func(c int32) int32 { return ROW + c } for i := int32(0); i < ROW; i++ { for j := int32(0); j < COL; j++ { // https://atcoder.jp/contests/abc259/editorial/4286 x := grid[i][j] if x > 0 { bm.Add2(rowId(i), colId(j), -x, 0, -x, -x) } if x < 0 { bm.Add2(rowId(i), colId(j), -x, 0, big, -x) } } } res, _ := bm.Calc() fmt.Fprintln(out, -res) } const INF int = 1e18 type BinaryOptimization struct { minimize bool n int32 source, sink int32 next int32 baseCost int edges map[[2]int32]int } func NewBinaryOptimization(n int32, minimize bool) *BinaryOptimization { return &BinaryOptimization{ minimize: minimize, n: n, source: n, sink: n + 1, next: n + 2, edges: make(map[[2]int32]int), } } // xi 属于 0/1 时对应的收益. func (bo *BinaryOptimization) Add1(i int32, x0, x1 int) { assert(0 <= i && i < bo.n, "i out of range") if !bo.minimize { x0, x1 = -x0, -x1 } bo._add_1(i, x0, x1) } // (xi,xj) = (00,01,10,11) 时对应的收益. // // !最小化代价时需要满足 x00 + x11 <= x01 + x10. // !最大化收益时需要满足 x00 + x11 >= x01 + x10. func (bo *BinaryOptimization) Add2(i, j int32, x00, x01, x10, x11 int) { assert(i != j, "i != j") assert(0 <= i && i < bo.n, "i out of range") assert(0 <= j && j < bo.n, "j out of range") if !bo.minimize { x00, x01, x10, x11 = -x00, -x01, -x10, -x11 } bo._add_2(i, j, x00, x01, x10, x11) } // (xi,xj,xk) = (000,001,010,011,100,101,110,111) 时对应的收益. func (bo *BinaryOptimization) Add3(i, j, k int32, x000, x001, x010, x011, x100, x101, x110, x111 int) { assert(i != j && i != k && j != k, "i != j && i != k && j != k") assert(0 <= i && i < bo.n, "i out of range") assert(0 <= j && j < bo.n, "j out of range") assert(0 <= k && k < bo.n, "k out of range") if !bo.minimize { x000, x001, x010, x011, x100, x101, x110, x111 = -x000, -x001, -x010, -x011, -x100, -x101, -x110, -x111 } bo._add_3(i, j, k, x000, x001, x010, x011, x100, x101, x110, x111) } // 返回最大收益/最小花费和每个变量的取值0/1. func (bo *BinaryOptimization) Calc() (int, []bool) { flow := NewMaxFlow(bo.next, bo.source, bo.sink) for key, cap := range bo.edges { from, to := key[0], key[1] flow.AddEdge(from, to, cap) } res, isCut := flow.Cut() res += bo.baseCost res = min(res, INF) if !bo.minimize { res = -res } assign := isCut[:bo.n] return res, assign } func (bo *BinaryOptimization) Debug() { fmt.Println("base_cost", bo.baseCost) fmt.Println("source=", bo.source, "sink=", bo.sink) for key, cap := range bo.edges { fmt.Println(key, cap) } } func (bo *BinaryOptimization) _add_1(i int32, x0, x1 int) { if x0 <= x1 { bo.baseCost += x0 bo._addEdge(bo.source, i, x1-x0) } else { bo.baseCost += x1 bo._addEdge(i, bo.sink, x0-x1) } } // x00 + x11 <= x01 + x10 func (bo *BinaryOptimization) _add_2(i, j int32, x00, x01, x10, x11 int) { if x00+x11 > x01+x10 { panic("need to satisfy `x00 + x11 <= x01 + x10`.") } bo._add_1(i, x00, x10) bo._add_1(j, 0, x11-x10) bo._addEdge(i, j, x01+x10-x00-x11) } func (bo *BinaryOptimization) _add_3(i, j, k int32, x000, x001, x010, x011, x100, x101, x110, x111 int) { p := x000 - x100 - x010 - x001 + x110 + x101 + x011 - x111 if p > 0 { bo.baseCost += x000 bo._add_1(i, 0, x100-x000) bo._add_1(j, 0, x010-x000) bo._add_1(k, 0, x001-x000) bo._add_2(i, j, 0, 0, 0, x000+x110-x100-x010) bo._add_2(i, k, 0, 0, 0, x000+x101-x100-x001) bo._add_2(j, k, 0, 0, 0, x000+x011-x010-x001) bo.baseCost -= p bo._addEdge(i, bo.next, p) bo._addEdge(j, bo.next, p) bo._addEdge(k, bo.next, p) bo._addEdge(bo.next, bo.sink, p) bo.next++ } else { p = -p bo.baseCost += x111 bo._add_1(i, x011-x111, 0) bo._add_1(i, x101-x111, 0) bo._add_1(i, x110-x111, 0) bo._add_2(i, j, x111+x001-x011-x101, 0, 0, 0) bo._add_2(i, k, x111+x010-x011-x110, 0, 0, 0) bo._add_2(j, k, x111+x100-x101-x110, 0, 0, 0) bo.baseCost -= p bo._addEdge(bo.next, i, p) bo._addEdge(bo.next, j, p) bo._addEdge(bo.next, k, p) bo._addEdge(bo.source, bo.next, p) bo.next++ } } // t>=0 func (bo *BinaryOptimization) _addEdge(i, j int32, t int) { if t == 0 { return } key := [2]int32{i, j} bo.edges[key] += t } type MaxFlow struct { caculated bool n, source, sink int32 flowRes int prog, level []int32 que []int32 pos [][2]int32 edges [][]edge } func NewMaxFlow(n, source, sink int32) *MaxFlow { return &MaxFlow{ n: n, source: source, sink: sink, prog: make([]int32, n), level: make([]int32, n), que: make([]int32, n), edges: make([][]edge, n), } } func (mf *MaxFlow) AddEdge(from, to int32, cap int) { mf.caculated = false if from < 0 || from >= mf.n { panic("from out of range") } if to < 0 || to >= mf.n { panic("to out of range") } if cap < 0 { panic("cap must be non-negative") } a := int32(len(mf.edges[from])) var b int32 if from == to { b = a + 1 } else { b = int32(len(mf.edges[to])) } mf.pos = append(mf.pos, [2]int32{from, a}) mf.edges[from] = append(mf.edges[from], edge{to: to, rev: b, cap: cap, flow: 0}) mf.edges[to] = append(mf.edges[to], edge{to: from, rev: a, cap: 0, flow: 0}) } func (mf *MaxFlow) Flow() int { if mf.caculated { return mf.flowRes } mf.caculated = true for mf.setLevel() { for i := range mf.prog { mf.prog[i] = 0 } for { f := mf.flowDfs(mf.source, INF) if f == 0 { break } mf.flowRes += f mf.flowRes = min(mf.flowRes, INF) if mf.flowRes == INF { return mf.flowRes } } } return mf.flowRes } // 返回最小割的值和每个点是否属于最小割. func (mf *MaxFlow) Cut() (int, []bool) { mf.Flow() isCut := make([]bool, mf.n) for i, v := range mf.level { isCut[i] = v < 0 } return mf.flowRes, isCut } func (mf *MaxFlow) setLevel() bool { for i := range mf.level { mf.level[i] = -1 } mf.level[mf.source] = 0 l, r := int32(0), int32(0) mf.que[r] = mf.source r++ for l < r { v := mf.que[l] l++ for _, e := range mf.edges[v] { if e.cap > 0 && mf.level[e.to] == -1 { mf.level[e.to] = mf.level[v] + 1 if e.to == mf.sink { return true } mf.que[r] = e.to r++ } } } return false } func (mf *MaxFlow) flowDfs(v int32, lim int) int { if v == mf.sink { return lim } res := 0 for i := &mf.prog[v]; *i < int32(len(mf.edges[v])); *i++ { e := &mf.edges[v][*i] if e.cap > 0 && mf.level[e.to] == mf.level[v]+1 { a := mf.flowDfs(e.to, min(lim, e.cap)) if a > 0 { e.cap -= a e.flow += a mf.edges[e.to][e.rev].cap += a mf.edges[e.to][e.rev].flow -= a res += a lim -= a if lim == 0 { break } } } } return res } type edge = struct { to, rev int32 cap, flow int } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } func min32(a, b int32) int32 { if a < b { return a } return b } func max32(a, b int32) int32 { if a > b { return a } return b } func assert(cond bool, msg string) { if !cond { panic(msg) } }