結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-28 02:34:16 |
言語 | Go (1.22.1) |
結果 |
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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 112 ms
20,576 KB |
testcase_08 | AC | 53 ms
10,576 KB |
testcase_09 | AC | 66 ms
14,324 KB |
testcase_10 | AC | 46 ms
8,720 KB |
testcase_11 | AC | 185 ms
24,476 KB |
testcase_12 | AC | 184 ms
24,644 KB |
testcase_13 | AC | 185 ms
24,608 KB |
testcase_14 | AC | 176 ms
22,404 KB |
testcase_15 | AC | 191 ms
26,408 KB |
testcase_16 | AC | 190 ms
26,228 KB |
testcase_17 | AC | 228 ms
21,820 KB |
testcase_18 | AC | 148 ms
24,856 KB |
testcase_19 | AC | 151 ms
28,800 KB |
testcase_20 | AC | 151 ms
28,824 KB |
testcase_21 | AC | 144 ms
23,736 KB |
20evil_special_uni1.txt | AC | 180 ms
25,236 KB |
20evil_special_uni2.txt | AC | 155 ms
24,036 KB |
ソースコード
package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) edges := make([][]int, 0, n-1) for i := 0; i < n-1; i++ { var u, v int fmt.Fscan(in, &u, &v) u, v = u-1, v-1 edges = 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, 0 colors := make([]int, n) // 0-left, 1-right for i := 0; i < n; i++ { colors[i] = -1 } var dfs func(u, c int) dfs = func(u, c int) { colors[u] = c if 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-1 rids := make([]int, n) // 二分图中的点在原图中的编号 0-n-1 => 0-n-1 c1, c2 := 0, 0 for i := 0; i < n; i++ { if colors[i] == 0 { ids[i] = c1 rids[c1] = i c1++ } else { ids[i] = c2 + L rids[c2+L] = i c2++ } } 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] = true for 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] = true q = append(q, v) } } } } bfs(g, n, 0, L) bfs(rg, n+1, L, n) return important } type BipartiteFlow struct { N, M, timeStamp int g, rg [][]int matchL, matchR []int dist []int used []int alive []bool matched 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] = -1 alive[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 = true for { bf.buildAugmentPath() bf.timeStamp++ flow := 0 for 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+1 func (bf *BipartiteFlow) BuildRisidualGraph() [][]int { if !bf.matched { bf.MaxMatching() } S := bf.N + bf.M T := bf.N + bf.M + 1 ris := 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] = true for len(que) > 0 { idx := que[0] que = que[1:] for _, to := range res[idx] { if visited[to] { continue } visited[to] = true que = 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] + 1 que = append(que, c) } } } } func (bf *BipartiteFlow) findMinDistAugmentPath(a int) bool { bf.used[a] = bf.timeStamp for _, 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] = a bf.matchL[a] = b return true } } return false }