最小カットの練習その2。問題:Dashboard - World Finals 2008 - Google Code Jam解法:最小カットを使って「燃やす埋める問題」を解くの54ページあたりから。引っかかったので一応実装について注意すると,'?'と'?'を結ぶ辺は1回しか結んではいけない。 一応ソ…

最小カットの練習がしたくなったので。問題:TopCoder Statistics - Problem Statement解法:最小カットを使って「燃やす埋める問題」を解くの40ページあたりから。 // max_flow const int MAX_V = 3000; const int INF = 1e6; class FordFulkerson { public: …

典型っぽい(解けるとは言っていない)。問題:木のグラフが与えられる。グラフの頂点のいくつかには数字が書いてあって,以下の条件を満たすように木を辺の切断によってグループ分けしたい。 ・数字の書いてある頂点が同じグループになってはいけない。 ・各グ…

お好み焼き食べたい・・・問題:お好み焼きをM人の友達で食べる。お好み焼きにはサイズという整数値があって,M人の間でサイズの差がK以下になるようにお好み焼きを選びたい。このような選び方は何通りあるか。解法:まずソートする。そして,それぞれの整数iに…