ARC098 F : Donation(1000)
作成日：2018.09.29
最終更新日：2018.09.29
問題概要
$1$から$N$までの番号が付いた$N$個の頂点と、$U_i$と$V_i$を結ぶ$M$本の辺からなる連結で単純な無向グラフがある。
$W$円持った状態で$A_s \leq W$を満たす頂点$s$を選びそこから出発し、操作1「所持金が$A_v$円以上である時、辺で隣接している頂点$v$に移動する」、操作2「今いる頂点$v$に$B_v$円寄付する」を所持金が負にならないように繰り返す。
操作2をすべての頂点で行えるような$W$の最小値を求めよ。
制約
$1 \leq N \leq 10^5$
$N-1 \leq M \leq 10^5$
$1 \leq A_i,B_i \leq 10^9$
$1 \leq U_i \lt V_i \leq N$
考え方
所持金は多いほうが良いので、操作2をできるだけ後、すなわち頂点$v$を最後に訪れる時に行うとして良い。
すると操作は「直前に削除した頂点から$A_u$が所持金以下であるような頂点$u$のみを通って行ける頂点$v$を$B_v$円払って削除する」と言い換えられる。
しかし、頂点を削除するのは考えにくいので逆向きに考える。
すなわち「所持金が$(A_v-B_v)$円以上である時、これまで訪れた頂点と辺でつながっている頂点$v$を訪れる」という操作を考える。
所持金の制約が$A_v-B_v$であるのは、元の操作においては頂点$v$を$A_v$円以上ある時に$B_v$円払って削除したからである。
初めに$w_0$円持っていたとすると、最終的には$(w_0 + \sum B_v)$円もっていることになる。
だから$w_0 \geq A_s - B_s$であるような頂点$s$から出発し、操作によってすべての頂点を訪れることのできるような$w_0$の最小値を求められれば良い。
$w_0$を固定して考える。
$s$となり得る頂点は複数存在することがあるが、これをすべて試すわけにはいかない。
そこですべての可能性を同時に考えることにする。
ある頂点$s$から出発した時に訪れることのできる頂点(このような頂点集合を$V$とする)から、別の頂点$s'$から出発した時に訪れることのできる頂点(このような頂点集合を$U$とする)を訪れることができると分かったとする。
$\sum_{v \in V} A_v$$\geq \sum_{u \in U} A_u$であれば、$A_u - B_u$$\leq w_0$$+ \sum_{u' \in U, u \neq u'} A_{u'}$($u \in U$)であることから$U$に含まれる頂点はすべて$s$から出発した時に訪れることができると分かる。
もし$\sum_{v \in V} A_v$$\lt \sum_{u \in U} A_u$であったとしたら、$s$,$V$と$s'$,$U$を逆にして考えれば$s'$から$V$に含まれるすべて頂点を訪れることができると分かる。
一度訪れることができると分かれば出発した頂点によって区別する必要はないから、単純に$U$と$V$を併合してしまえば良い。
以上より$w_0 \geq$$A_v - B_v$を満たすすべての頂点$v$を訪れることができるとし、訪れることができると分かっている連結成分$V$から辺でつながっていて$A_u - B_u$$\leq w_0$$+ \sum_{v' \in V}A_{v'}$となるような頂点$u$の属する連結成分$U$を$V$と併合することを繰り返していき、すべての頂点を併合できるかで判定すれば良い。
頂点集合$V$が持つべきものは、$\sum_{v \in V} B_v$と辺でつながっている頂点の集合である。
前者の併合は単なる足し算ででき、後者の併合は「マージする時の一般的なテク」を用いて行えば良い。
後は併合できる頂点集合を見つけられれば良いが、愚直にやると$O(MN)$となるので工夫する。
併合できる頂点$u$は$A_u - B_u$$\leq w_0$$+ \sum_{v' \in V}A_{v'}$を満たさなけれならないから、頂点は$A_u - B_u$が小さいものから順番に見ていけば良い。
よって$V$と辺でつながっている頂点の集合をpriority_queueで持っておき、$A_u-B_u$が小さいものから併合できなくなるまで見ていけば良い。
また併合できなかった頂点が併合できるようになるには$V$の要素が増えた時のみであるから、併合した後の頂点集合をqueue等に詰めて順に確認していけば良い。
以上より条件を満たす$w_0$の最小値は二分探索で求められる。
ボトルネックはpriority_queueの併合であるから、計算量は$O(M (log \: M)^2 log \: max(A_i))$である。
これはかなりギリギリ($2$sec制限で$1.3$sec)であるが間に合う。
ソースコード
マクロ等はこちら
const int MC = 1e5 + 3;
class UF{
int x[MC];
LL p[MC];
priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> Q[MC];
public:
void clear(){
fill(x,x+MC,-1);
fill(p,p+MC,0);
repp(i,0,MC) while(!Q[i].empty()) Q[i].pop();
}
int boss(int a){
int s = a;
while(x[s] > -1) s = x[s];
if(s != a) x[a] = s;
return s;
}
void uni(int a , int b){
int s = boss(a);
int t = boss(b);
if(s != t){
if(Q[s].size() < Q[t].size()) swap(s,t);
while(!Q[t].empty()){
Q[s].push(Q[t].top());
Q[t].pop();
}
if(x[s] < x[t]){
x[s] += x[t];
x[t] = s;
p[s] += p[t];
} else {
x[t] += x[s];
x[s] = t;
p[t] += p[s];
swap(Q[s],Q[t]);
}
}
}
LL get_p(int a){
return p[boss(a)];
}
int get_q(int a){
a = boss(a);
return Q[a].empty()?-1:Q[a].top().second;
}
void set(int a , LL b){
p[a] = b;
}
void push(int a , int b , LL c){
Q[a].push({c,b});
}
void pop(int a){
Q[boss(a)].pop();
}
};
int N,M;
LL A[MC],B[MC],S;
vector<int> V[MC];
UF uf;
bool eval(LL z){
vector<int> used(N,0);
queue<int> Q;
uf.clear();
repp(i,0,N){
for(auto u : V[i]) uf.push(i,u,A[u]);
if(z >= A[i]){
Q.push(i);
uf.set(i,B[i]);
used[i] = 1;
}
}
while(!Q.empty()){
int k = Q.front(); Q.pop();
for(int u = uf.get_q(k) ; u >= 0 && z + uf.get_p(k) >= A[u] ; u = uf.get_q(k)){
if(!used[u]){
Q.push(u);
uf.set(u,B[u]);
used[u] = 1;
}
uf.pop(k);
uf.uni(k,u);
}
}
int c = 0;
repp(i,0,N) c += used[i];
return c == N;
}
LL BS(LL x , LL y){
if(x-y<2) return x;
LL z = (x+y)/2;
return eval(z)?BS(z,y):BS(x,z);
}
int main(){
cin >> N >> M;
repp(i,0,N){
cin >> A[i] >> B[i];
S += B[i];
A[i] -= B[i];
}
repp(i,0,M){
int x,y; cin >> x >> y;
V[--x].push_back(--y);
V[y].push_back(x);
}
cout << S + BS(1e9,-1) << endl;
return 0;
}解法まとめ
二分探索で最終的に残る所持金$z$の最小値$z_0$を求める。
答えは$z_0$$+ \sum B_i$となる。(101-105,111,119行)
$z$を固定するごとにすべての頂点を訪れることができるかを次のように判定する。
まず$z \geq A_i - B_i$(ソースコードでは$A_i$がこの値を保持していることに注意;112行)となる頂点$i$を訪問可能とする。(76-83行)
次に新たに訪問可能または併合された頂点集合$V$に対して、それらと辺で結ばれている頂点$u$を$A_u - B_u$が小さい順に見ていき、$A_u - B_u$$\leq z$$+ \sum_{k \in V} B_k$を満たすものを併合していく。(84-95行)
すべての頂点を訪問できれば、固定された$z$は解となり得ると分かる。(96-98行)