結果

問題 No.768 Tapris and Noel play the game on Treeone
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-28 02:34:16
言語 Go
(1.22.1)
結果
AC  
実行時間 255 ms / 2,000 ms
コード長 5,870 bytes
コンパイル時間 14,187 ms
コンパイル使用メモリ 217,368 KB
実行使用メモリ 31,240 KB
最終ジャッジ日時 2023-10-19 23:36:01
合計ジャッジ時間 20,346 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 133 ms
18,588 KB
testcase_08 AC 61 ms
12,400 KB
testcase_09 AC 79 ms
12,480 KB
testcase_10 AC 56 ms
8,640 KB
testcase_11 AC 228 ms
21,944 KB
testcase_12 AC 229 ms
24,844 KB
testcase_13 AC 220 ms
22,808 KB
testcase_14 AC 228 ms
24,588 KB
testcase_15 AC 245 ms
22,388 KB
testcase_16 AC 242 ms
22,604 KB
testcase_17 AC 255 ms
29,192 KB
testcase_18 AC 186 ms
31,240 KB
testcase_19 AC 184 ms
30,052 KB
testcase_20 AC 175 ms
27,796 KB
testcase_21 AC 169 ms
27,124 KB
20evil_special_uni1.txt AC 220 ms
27,076 KB
20evil_special_uni2.txt AC 209 ms
23,408 KB
権限があれば一括ダウンロードができます

ソースコード

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
}

// 指定左侧点数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
}
0