#1002546 (Go) No.2320 Game World for PvP

提出ソース

結果

問題	No.2320 Game World for PvP
ユーザー	草苺奶昔
提出日時	2024-08-19 23:15:36
言語	Go (1.22.1)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	9,473 bytes
コンパイル時間	13,828 ms
コンパイル使用メモリ	222,024 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-08-19 23:15:51
合計ジャッジ時間	13,240 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,812 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	3 ms 6,944 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	4 ms 6,944 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	4 ms 6,944 KB
testcase_10	AC	4 ms 6,944 KB
testcase_11	AC	4 ms 6,940 KB
testcase_12	AC	4 ms 6,944 KB
testcase_13	AC	4 ms 6,944 KB
testcase_14	AC	3 ms 6,940 KB
testcase_15	AC	4 ms 6,944 KB
testcase_16	AC	3 ms 6,940 KB
testcase_17	AC	4 ms 6,940 KB
testcase_18	AC	4 ms 6,940 KB
testcase_19	AC	4 ms 6,944 KB
testcase_20	AC	4 ms 6,944 KB
testcase_21	AC	4 ms 6,940 KB
testcase_22	AC	4 ms 6,944 KB
testcase_23	AC	4 ms 6,944 KB
testcase_24	AC	4 ms 6,940 KB
testcase_25	AC	4 ms 6,944 KB
testcase_26	AC	4 ms 6,944 KB
testcase_27	AC	1 ms 6,944 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	3 ms 6,940 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	3 ms 6,944 KB
testcase_32	AC	1 ms 6,944 KB
testcase_33	AC	3 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	// yuki_1541()
	yuki_2320()
}

// 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.Println(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.Println(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)
	}
}