結果
問題 | No.2320 Game World for PvP |
ユーザー |
|
提出日時 | 2024-08-19 23:15:36 |
言語 | Go (1.23.4) |
結果 |
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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
package mainimport ("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 int32var base intfmt.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 intfmt.Fscan(in, &k, &cost)costs[i] = costsubjects[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 int32fmt.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 = 1e18type BinaryOptimization struct {minimize booln int32source, sink int32next int32baseCost intedges 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.baseCostres = 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 += x0bo._addEdge(bo.source, i, x1-x0)} else {bo.baseCost += x1bo._addEdge(i, bo.sink, x0-x1)}}// x00 + x11 <= x01 + x10func (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 - x111if p > 0 {bo.baseCost += x000bo._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 -= pbo._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 = -pbo.baseCost += x111bo._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 -= pbo._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>=0func (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 booln, source, sink int32flowRes intprog, level []int32que []int32pos [][2]int32edges [][]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 = falseif 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 int32if 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 = truefor mf.setLevel() {for i := range mf.prog {mf.prog[i] = 0}for {f := mf.flowDfs(mf.source, INF)if f == 0 {break}mf.flowRes += fmf.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] = 0l, r := int32(0), int32(0)mf.que[r] = mf.sourcer++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] + 1if e.to == mf.sink {return true}mf.que[r] = e.tor++}}}return false}func (mf *MaxFlow) flowDfs(v int32, lim int) int {if v == mf.sink {return lim}res := 0for 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 -= ae.flow += amf.edges[e.to][e.rev].cap += amf.edges[e.to][e.rev].flow -= ares += alim -= aif lim == 0 {break}}}}return res}type edge = struct {to, rev int32cap, 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)}}