AtCoder ARC #115 : F - Migration

問題文がヒントになってたな…。
https://atcoder.jp/contests/arc115/tasks/arc115_f

問題

木を成す無向グラフが与えられる。
各頂点には整数値が書いてある。
今、K個の駒があり、それぞれ初期位置と移動先の位置が与えられる。

任意の駒を選び、辺に沿って隣接頂点に動かす、という作業を繰り返し、駒を指定の移動先まで移動させたい。
その際、移動のたびに、駒のいる頂点に書かれた整数値の総和(ポテンシャルと呼ぶ)を計算することを考える。
この手順において、ポテンシャルの最大値を最小化したい。その値を求めよ。

解法

このルールでは、ある一連の駒の移動と、その逆順の移動では、ポテンシャルの最大値は同一となる。
そこで、駒を初期位置から移動先に動かすのではなく、双方から同じ状態にもっていくことを考えよう。
今、ある駒を選び、今より小さな整数値の頂点に移動することを考える。その際、場合によっては今より大きな整数値の頂点を経由しなければならないこともある。

そこで、各頂点について、移動先を「今より小さな整数値の頂点のうち、経由しなければいけない整数値の頂点の最大値が最小の点」と一意に決めよう。
移動が完了すると、駒のいる頂点の整数値の総和は移動前より小さくなるので、最大値を更新する危険性が低くなる。

あとは貪欲法で解く。
初期位置及び移動先の位置から、それぞれの駒の位置のsetが一致するまで、駒を移動先に移動させていく。
その際は、経由する整数値の最大値によって、ポテンシャルの最大値を更新しにくいもの、すなわち移動前と経由する整数値の最大値の差が最小のものをどん欲に選び、移動させていく。

int N;
int H[2020];
pair<int,int> P[2020];
int order[2020];
vector<int> E[2020];
int K;
int V[2][2020];

int nex[2020],dif[2020];
ll D[2020];

void dfs(int cur,int pre,int ma) {
	ma=max(ma,H[cur]);
	D[cur]=ma;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,ma);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i];
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	FOR(i,N) {
		dfs(i,i,0);
		D[i]=1<<30;
		nex[i]=i;
		FOR(j,N) if(H[j]<H[i]||(H[j]==H[i]&&j<i)) {
			if(D[j]<D[nex[i]]) nex[i]=j;
		}
		dif[i]=D[nex[i]]-H[i];
	}
	
	cin>>K;
	ll P[2]={};
	ll ma;
	int same=0;
	priority_queue<pair<int,int>> Q;
	FOR(i,K) {
		cin>>V[0][i]>>V[1][i];
		V[0][i]--,V[1][i]--;
		P[0]+=H[V[0][i]];
		P[1]+=H[V[1][i]];
		if(V[0][i]==V[1][i]) same++;
		Q.push({-dif[V[0][i]],i*2});
		Q.push({-dif[V[1][i]],i*2+1});
	}
	ma=max(P[0],P[1]);
	while(same<K) {
		int cur=Q.top().second/2;
		int id=Q.top().second%2;
		Q.pop();
		
		if(V[0][cur]==V[1][cur]) same--;
		
		ma=max(ma,P[id]+dif[V[id][cur]]);
		P[id]-=H[V[id][cur]]-H[nex[V[id][cur]]];
		V[id][cur]=nex[V[id][cur]];
		Q.push({-dif[V[id][cur]],cur*2+id});
		
		if(V[0][cur]==V[1][cur]) same++;
	}
	cout<<ma<<endl;
}

まとめ

双方向から、より低いポテンシャルの状態にもっていく、と考えるとわかりやすいね。