結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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
}
// nm.
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.uv.
// !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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0