ARC085 E : MUL(700)
作成日：2017.11.12
最終更新日：2017.11.13
▼更新履歴
- 2017.11.13
Project Selection Problemの説明を修正・加筆
問題概要
宝石が$N$個あり、それぞれ$1$から$N$の互いに異なる整数が書かれている。
$i$が書かれた宝石は$a_i$の価値がある。
操作「正整数$x$を選び、$x$の倍数が書かれた宝石を割る」を$0$回以上行い、割られていない宝石の価値の総和を最大化する。
この最大値を求めよ。
制約
$1 \leq N \leq 100$
$|a_i| \leq 10^9$
入力はすべて整数
考え方
注意
この問題は知識を必要とする典型問題なので、考察の過程は一切書いていない。
より詳しくは「最小カットを使って「燃やす埋める問題」を解く」を参照のこと。
Project Selection Problemと呼ばれる問題である。
すなわち、要素を選ぶか否かの選択と、ある要素を選ぶと同時にある別の要素を選ばない状況に対して費用がかかる時、その費用を最小化する問題である。
前者において費用がかかる代わりに利益が得られる時は、初めからその利益を得たものとして利益が得られない状況に費用がかかると考える。
また後者において費用がかかる代わりにそのような選択が禁止されている場合、無限の費用がかかるものとみなす。
要素$i$を選ぶ時に$c_i$だけ、選ばない時に$d_i$だけ費用がかかり、$x_j$を選んで$y_j$を選ばなかった時に費用が$z_j$だけかかるとする。
そして始点から$i$に容量$c_i$の辺、$i$から終点に容量$d_i$の辺、$y_j$から$x_j$に容量$z_j$の辺を張ったネットワークを作る。
するとこのネットワークを始点側に選ばない要素、終点側に選ぶ要素が来るようにカットすることを考えれば、最小カットの値が求めるものであることが分かる。
以上のことを踏まえると、今回の場合は以下のネットワークの最小カットが求まれば良い。
$i$が書かれた宝石を頂点$i$に対応させる。
$a_i$が負の時は始点から$i$に容量$-a_i$の辺、そうでない時は$i$から終点に容量$a_i$の辺を張る。
さらに、各$x$に対して$x$から$cx$($c \geq 2$)に容量無限大の辺を張る。
最大フロー最小カット定理より、最小カットを求める代わりに最大流量を求めれば良い。
このネットワークの頂点は$O(N)$個、辺は$O(N log \: N)$本であるから、Edmonds-Karp法で十分高速である。
ソースコード
マクロ等はこちら
Edmonds_Karp<T>
void put(int a , int b , T c)
始点$a$、終点$b$、容量$c$の辺をグラフに追加
T ans(int s , int t)
$s$を始点、$t$を終点とする時のグラフの最大流を取得
const LL INF = 1234567890123456;
int N;
LL s;
Edmonds_Karp<LL> solve;
int main(){
cin >> N;
repp(i,1,N+1){
int a;
cin >> a;
if(a<0){
solve.put(0,i,-a);
} else {
solve.put(i,N+1,a);
s += a;
}
for(int k = i*2 ; k <= N ; k += i) solve.put(i,k,INF);
}
cout << s - solve.ans(0,N+1) << endl;
return 0;
}解法まとめ
$a_i$が負の時は始点から$i$に容量$-a_i$の辺、そうでない時は$i$から終点に容量$a_i$の辺を張る。(11-16行)
さらに、各$x$に対して$x$から$cx$($c \geq 2$)に容量無限大の辺を張る。(17行)
$a_i$で正のものの総和$s$からこのネットワークの最大流量を引いたものが答えである。(19行)