kmjp's blog

競技プログラミング参加記です

AtCoder ARC #098 : F - Donation

これ系の問題、本番で解ける気がしない。
https://beta.atcoder.jp/contests/arc098/tasks/arc098_d

問題

連結無向グラフが与えられる。
各頂点vにはパラメータA[v],B[v]がある。
今の所持金をWとすると、頂点vに進入するにはWがA[v]以上でなければならない。
また、所持金がB[v]以上ある場合、所持金のうちB[v]を寄付することができる。

任意の頂点から初めて隣接頂点を辿りながら移動および寄付する場合、全頂点に寄付するのに必要な初期状態の金額を求めよ。

解法

この動作を巻き戻すと以下のようになる。

  • 今いる頂点に初めて来ると所持金がB[v]増える。
  • 今所持金がA[v]以上ある場合、任意の隣接頂点に移動できる。

寄付前の時点で進入に対し、必要な追加金額をC[v]=max(A[v]-B[v],0)とする。
上記条件を考えると、所持金がC[v]あればその頂点に進入し、B[v]得てまた隣接頂点に移動できることになる。

そう考えるとC[v]の小さい順に訪れるのが良いが、かといってC[v]の大きな頂点が間にあると必ずしもそうはいかない。
C[v]の大きな頂点があるとき、そこに隣接するC[v]以下の頂点で構成された連結成分を考える。
その際、個々の連結成分内を全部訪問するのに必要な最小金額を求め、最初にそちらを訪問した後C[v]の頂点を訪問し、残った連結成分を全部辿る場合に必要な最小金額を考えよう。

これをC[v]の小さい順に行い、Union-Findで訪問済み頂点を連結させながら処理していくとよい。

int N,M;
ll A[101010],B[101010];
pair<ll,int> C[101010];
vector<int> E[101010];
ll BS[101010];
ll Q[101010];
int did[101010];
template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		C[i]={max(A[i]-B[i],0LL),i};
		BS[i]=B[i];
	}
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	sort(C,C+N);
	FOR(i,N) {
		x=C[i].second;
		did[x]=1;
		vector<int> V;
		FORR(e,E[x]) if(did[e]==1) V.push_back(uf[e]);
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		
		ll BSS=BS[x];
		FORR(e,V) BSS+=BS[e];
		
		Q[x]=C[i].first+BSS;
		FORR(e,V) Q[x]=min(Q[x],max(Q[e],C[i].first)+BSS-BS[e]);
		FORR(e,V) uf(e,x);
		Q[uf[x]]=Q[x];
		BS[uf[x]]=BSS;
		
	}
	cout<<Q[uf[0]]<<endl;
	
}

まとめ

これも後退解析に入るのかな?