AOJ-ICPC 2016.10.9 - ああああ

実装軽いやつ

問題

問題概要

各連結成分が強連結なグラフが与えられる。
各頂点について、入ってくる辺と出ていく辺の重みが等しくなるようにすると、
一部の辺の重みを隠しても復元することができる。
最大でいくつの辺の重みを隠せるか。

解法

ある頂点の入ってくる辺の重みが全てわかっているとすると、出ていく辺のうち1つを隠すことができる。
全ての頂点について、出ていく辺の1つを隠すと入ってくる辺の重み全てが分かる頂点がなくなるので、ある頂点だけは全ての辺をそのままにしておく。
各連結成分についてこれが言えるので、連結成分ごとに $|edge| + |verticle| - 1$ が答えとなるのでこれを全て足せば良い。

source

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2025401#1

問題

Enumeration | Aizu Online Judge

問題概要

省略

解法

高速メビウス変換。
高速メビウス変換はある集合の全ての部分集合についてandの条件の場合の値が求まっている時、
全ての部分集合についてorの条件の場合の値を $O(2^{N})$ で求めることができる。逆の操作として高速ゼータ変換がある。
この問題は高速メビウス変換するだけなのだが、long long でもオーバーフローするのでいい感じにしてやる必要がある。