結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
|
提出日時 | 2023-03-28 02:34:16 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 5,870 bytes |
コンパイル時間 | 14,007 ms |
コンパイル使用メモリ | 222,828 KB |
実行使用メモリ | 28,824 KB |
最終ジャッジ日時 | 2024-09-19 19:29:44 |
合計ジャッジ時間 | 18,428 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
package mainimport ("bufio""fmt""os")func main() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)edges := make([][]int, 0, n-1)for i := 0; i < n-1; i++ {var u, v intfmt.Fscan(in, &u, &v)u, v = u-1, v-1edges = append(edges, []int{u, v})}res := solve(n, edges)cand := []int{}for i, v := range res {if !v {cand = append(cand, i+1)}}fmt.Fprintln(out, len(cand))for _, v := range cand {fmt.Fprintln(out, v)}}// 判断二分图中每个点是否`一定`存在于最大匹配中(删去这个点之后,最大流减小)// 保证图是二分图func solve(n int, edges [][]int) []bool {adjList := make([][]int, n)for _, e := range edges {u, v := e[0], e[1]adjList[u] = append(adjList[u], v)adjList[v] = append(adjList[v], u)}L, R := 0, 0colors := make([]int, n) // 0-left, 1-rightfor i := 0; i < n; i++ {colors[i] = -1}var dfs func(u, c int)dfs = func(u, c int) {colors[u] = cif c == 0 {L++} else {R++}for _, v := range adjList[u] {if colors[v] == -1 {dfs(v, c^1)}}}for i := 0; i < n; i++ {if colors[i] == -1 {dfs(i, 0)}}ids := make([]int, n) // 原图中的点在二分图中的编号 左边:0-L-1 右边:L-n-1rids := make([]int, n) // 二分图中的点在原图中的编号 0-n-1 => 0-n-1c1, c2 := 0, 0for i := 0; i < n; i++ {if colors[i] == 0 {ids[i] = c1rids[c1] = ic1++} else {ids[i] = c2 + Lrids[c2+L] = ic2++}}bf := NewBipartiteFlow(L, R)for _, e := range edges {u, v := e[0], e[1]if colors[u] == 1 {u, v = v, u}bf.AddEdge(ids[u], ids[v]-L)}g := bf.BuildRisidualGraph() // 残量网络rg := make([][]int, len(g)) // 残量网络的反图for i := 0; i < len(g); i++ {for _, v := range g[i] {rg[v] = append(rg[v], i)}}important := make([]bool, n)for i := range important {important[i] = true}bfs := func(graph [][]int, start, begin, end int) {vis := make([]bool, len(graph))q := []int{start}vis[start] = truefor len(q) > 0 {cur := q[0]q = q[1:]if begin <= cur && cur < end {important[rids[cur]] = false // 从虚拟源点出发能到达的左侧点/从虚拟汇点出发能到达的右侧点}for _, v := range graph[cur] {if !vis[v] {vis[v] = trueq = append(q, v)}}}}bfs(g, n, 0, L)bfs(rg, n+1, L, n)return important}type BipartiteFlow struct {N, M, timeStamp intg, rg [][]intmatchL, matchR []intdist []intused []intalive []boolmatched bool}// 指定左侧点数n,右侧点数m,初始化二分图最大流.func NewBipartiteFlow(n, m int) *BipartiteFlow {g, rg := make([][]int, n), make([][]int, m)matchL, matchR := make([]int, n), make([]int, m)used, alive := make([]int, n), make([]bool, n)for i := 0; i < n; i++ {matchL[i] = -1alive[i] = true}for i := 0; i < m; i++ {matchR[i] = -1}return &BipartiteFlow{N: n,M: m,g: g,rg: rg,matchL: matchL,matchR: matchR,used: used,alive: alive,}}// 增加一条边u-v.u属于左侧点集,v属于右侧点集.// !0<=u<n,0<=v<m.func (bf *BipartiteFlow) AddEdge(u, v int) {bf.g[u] = append(bf.g[u], v)bf.rg[v] = append(bf.rg[v], u)}// 求最大匹配.// 返回(左侧点,右侧点)的匹配对.// !0<=左侧点<n,0<=右侧点<m.func (bf *BipartiteFlow) MaxMatching() [][2]int {bf.matched = truefor {bf.buildAugmentPath()bf.timeStamp++flow := 0for i := 0; i < bf.N; i++ {if bf.matchL[i] == -1 {tmp := bf.findMinDistAugmentPath(i)if tmp {flow++}}}if flow == 0 {break}}res := [][2]int{}for i := 0; i < bf.N; i++ {if bf.matchL[i] >= 0 {res = append(res, [2]int{i, bf.matchL[i]})}}return res}// 构建残量图.// left: [0,n), right: [n,n+m), S: n+m, T: n+m+1func (bf *BipartiteFlow) BuildRisidualGraph() [][]int {if !bf.matched {bf.MaxMatching()}S := bf.N + bf.MT := bf.N + bf.M + 1ris := make([][]int, bf.N+bf.M+2)for i := 0; i < bf.N; i++ {if bf.matchL[i] == -1 {ris[S] = append(ris[S], i)} else {ris[i] = append(ris[i], S)}}for i := 0; i < bf.M; i++ {if bf.matchR[i] == -1 {ris[i+bf.N] = append(ris[i+bf.N], T)} else {ris[T] = append(ris[T], i+bf.N)}}for i := 0; i < bf.N; i++ {for _, j := range bf.g[i] {if bf.matchL[i] == j {ris[j+bf.N] = append(ris[j+bf.N], i)} else {ris[i] = append(ris[i], j+bf.N)}}}return ris}func (bf *BipartiteFlow) findResidualPath() []bool {res := bf.BuildRisidualGraph()que := []int{}visited := make([]bool, bf.N+bf.M+2)que = append(que, bf.N+bf.M)visited[bf.N+bf.M] = truefor len(que) > 0 {idx := que[0]que = que[1:]for _, to := range res[idx] {if visited[to] {continue}visited[to] = trueque = append(que, to)}}return visited}func (bf *BipartiteFlow) buildAugmentPath() {que := []int{}bf.dist = make([]int, len(bf.g))for i := 0; i < len(bf.g); i++ {bf.dist[i] = -1}for i := 0; i < bf.N; i++ {if bf.matchL[i] == -1 {que = append(que, i)bf.dist[i] = 0}}for len(que) > 0 {a := que[0]que = que[1:]for _, b := range bf.g[a] {c := bf.matchR[b]if c >= 0 && bf.dist[c] == -1 {bf.dist[c] = bf.dist[a] + 1que = append(que, c)}}}}func (bf *BipartiteFlow) findMinDistAugmentPath(a int) bool {bf.used[a] = bf.timeStampfor _, b := range bf.g[a] {c := bf.matchR[b]if c < 0 || (bf.used[c] != bf.timeStamp && bf.dist[c] == bf.dist[a]+1 && bf.findMinDistAugmentPath(c)) {bf.matchR[b] = abf.matchL[a] = breturn true}}return false}