結果

問題 No.1541 ゅゅさんのテスト勉強
コンテスト
ユーザー 草苺奶昔
提出日時 2023-03-14 13:08:36
言語 Go
(1.23.4)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 3,709 bytes
コンパイル時間 12,756 ms
コンパイル使用メモリ 235,840 KB
実行使用メモリ 7,880 KB
最終ジャッジ日時 2024-09-18 08:01:17
合計ジャッジ時間 13,374 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {
	// https://yukicoder.me/problems/no/1541
	// 期末考试
	// 有n个考试科目,每学一个科目就能多拿base分
	// 对于每个科目i,可以花费cost来学习，学习之后有额外的收益:
	// 对于科目subjects[j],如果i和subjects[j]都学习了,那么就能多拿到bonus[j]分
	// !最大化(总分-花费)
	// n<=100

	// !每个科目学还是不学 => 燃やす埋める
	// 先学习所有科目,然后再割掉不学每个科目的代价(最小割)

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, base int
	fmt.Fscan(in, &n, &base)

	flow := NewMaxFlowGraph(n + 2 + n*n)
	S, T := n, n+1 // !S:不学 T:学
	ptr := n + 2

	res := 0
	for i := 0; i < n; i++ {
		var k, cost int
		fmt.Fscan(in, &k, &cost)

		subjects := make([]int, k)
		for j := 0; j < k; j++ {
			fmt.Fscan(in, &subjects[j])
			subjects[j]--
		}

		bonus := make([]int, k)
		for j := 0; j < k; j++ {
			fmt.Fscan(in, &bonus[j])
		}

		res += base
		flow.AddEdge(S, i, cost) // 学失去cost分
		flow.AddEdge(i, T, base) // 不学失去base分
		for j := 0; j < k; j++ {
			res += bonus[j]
			flow.AddEdge(i, ptr, INF)
			flow.AddEdge(subjects[j], ptr, INF)
			flow.AddEdge(ptr, T, bonus[j]) // 学了i并且学了subjects[j]，此时不学subjects[j]失去bonus[j]分
			ptr++                          // !ptr表示状态:学了i并且学了subjects[j]
		}
	}

	fmt.Fprintln(out, res-flow.Flow(S, T))
}

const INF int = 1e18

type Edge struct{ to, rev, cap int }
type MaxFlowGraph struct {
	N           int
	G           [][]Edge
	prog, level []int
	flowRes     int
	calculated  bool
}

func NewMaxFlowGraph(n int) *MaxFlowGraph {
	return &MaxFlowGraph{N: n, G: make([][]Edge, n)}
}

func (g *MaxFlowGraph) AddEdge(from, to, cap int) {
	g.G[from] = append(g.G[from], Edge{to, len(g.G[to]), cap})
	g.G[to] = append(g.G[to], Edge{from, len(g.G[from]) - 1, 0})
}

func (g *MaxFlowGraph) Flow(source, sink int) int {
	if g.calculated {
		return g.flowRes
	}
	g.calculated = true
	for g.setLevel(source, sink) {
		g.prog = make([]int, g.N)
		for {
			f := g.flowDfs(source, sink, INF)
			if f == 0 {
				break
			}
			g.flowRes += f
			g.flowRes = min(g.flowRes, INF)
			if g.flowRes == INF {
				return g.flowRes
			}
		}
	}
	return g.flowRes
}

// 返回最小割的值和每个点是否属于最小割
func (g *MaxFlowGraph) Cut(source, sink int) (minCut int, isCut []bool) {
	minCut = g.Flow(source, sink)
	isCut = make([]bool, g.N)
	for i := 0; i < g.N; i++ {
		isCut[i] = g.level[i] < 0
	}
	return
}

// 残量图的边(from,to,remainCap)
func (g *MaxFlowGraph) GetEdges() (edges [][3]int) {
	for v := 0; v < g.N; v++ {
		for _, e := range g.G[v] {
			edges = append(edges, [3]int{v, e.to, e.cap})
		}
	}
	return
}

func (g *MaxFlowGraph) setLevel(source, sink int) bool {
	g.level = make([]int, g.N)
	for i := range g.level {
		g.level[i] = -1
	}
	g.level[source] = 0
	q := []int{source}
	for len(q) > 0 {
		v := q[0]
		q = q[1:]
		for _, e := range g.G[v] {
			if e.cap > 0 && g.level[e.to] == -1 {
				g.level[e.to] = g.level[v] + 1
				if e.to == sink {
					return true
				}
				q = append(q, e.to)
			}
		}
	}
	return false
}

func (g *MaxFlowGraph) flowDfs(v, sink, lim int) int {
	if v == sink {
		return lim
	}
	res := 0
	for i := &g.prog[v]; *i < len(g.G[v]); *i++ {
		e := &g.G[v][*i]
		if e.cap > 0 && g.level[e.to] == g.level[v]+1 {
			a := g.flowDfs(e.to, sink, min(lim, e.cap))
			if a > 0 {
				e.cap -= a
				g.G[e.to][e.rev].cap += a
				res += a
				lim -= a
				if lim == 0 {
					break
				}
			}
		}
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
0