結果

問題 No.1640 簡単な色塗り
ユーザー 小野寺健
提出日時 2021-11-29 14:21:53
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,183 bytes
コンパイル時間 48 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 76,064 KB
最終ジャッジ日時 2024-07-02 11:28:48
合計ジャッジ時間 6,251 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 51
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

N = gets.to_i

$G = Array.new(N*2+2){Array.new} 

def add_edge(from, to, cap)
	$G[from] << [to, cap, $G[to].length]
	$G[to] << [from, 0, $G[from].length - 1]
end

def bfs(s)
	$level = Array.new(N*2+2, -1)
	$level[s] = 0
	que = [s]
	while que.length > 0 do
		v = que.shift
		$G[v].each {|to, cap, rev|
			if cap > 0 and $level[to] < 0 then
				$level[to] = $level[v] + 1
				que << to
			end
		}
	end
end

def dfs(v, t, f)
	return f if v == t
	$G[v].each {|e|
		if e[1] > 0 and $level[v] < $level[e[0]] then
			d = dfs(e[0], t, [f, e[1]].min)
			if d > 0 then
				e[1] -= d
				$G[e[0]][e[2]][1] += d
				return d
			end
		end
	}
	return 0
end

def max_flow(s, t)
	flow = 0
	loop {
		bfs(s)
		return flow if $level[t] < 0
		f = dfs(s, t, Float::INFINITY)
		while f > 0 do
			flow += f
			f = dfs(s, t, Float::INFINITY)
		end
	}
end

s = 0
t = 2 * N + 1

1.upto(N) {|i|
	add_edge(s, i, 1)
}
(N+1).upto(2*N) {|i|
	add_edge(i, t, 1)
}

1.upto(N) { |i|
	a, b = gets.split(" ").map{|s| s.to_i}
	add_edge(i, a + N, 1)
	add_edge(i, b + N, 1)
}

n = max_flow(s, t)

if n == N then
	puts "Yes"
	1.upto(N) {|i|
		$G[i].each{|to, cap, rev|
			puts (to - N) if cap == 0
		}
	}
else
	puts "No"
end
0