全国統一プログラミング王決定戦予選 : E - Weights on Vertices and Edges

苦戦しすぎた。
https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e

問題

頂点と辺にそれぞれ重みをもつ無向グラフが与えられる。
このグラフを以下のように変形したい。

• 各連結成分において、頂点の重みの総和は、各辺の重み以上である。

変形では、できるだけ少ない数の辺を削除することとしたい。最小何本の辺を削除すれば条件を満たせるか。

解法

Union-Findでクラスカル法の要領で頂点を連結させるのを、巻き戻していくことを考える。
連結成分内の最大重みの辺が、連結成分内の頂点の重みの和より大きいならその辺を削除しないといけない。
逆に、和以下であるならその連結成分はそのまま残すことができる。

Union-Findのデータ構造を任意順で巻き戻すことはできないが、Union-Findで連結頂点を組み合わせていく様子を二分木で表現してみよう。
（連結する際は、新規頂点を作り両連結成分の代表点２点とつなげる）

連結成分内をさらに分解する方向で探索する・しないは、この二分木上でDFSを続ける・打ち切るに相当する。
これにより各辺を削除すべきか判定していこう。
元々クラスカル法の時点で最小全域木に含まれなかった辺は、最後に連結成分が確定後再度確認すればよい。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<500000> uf;

int N,M;
ll X[201010];
int A[101010],B[101010];
ll Y[101010];
pair<ll,int> P[101010];
int top[202020];
vector<int> E[201010];
int num[202020];
int ok[202020];

void dfs2(int cur) {
	if(cur<N) return;
	ok[E[cur][0]]=1;
	dfs2(E[cur][1]);
	dfs2(E[cur][2]);
}

void dfs(int cur) {
	if(cur<N) return;
	
	if(Y[E[cur][0]]<=X[cur]) {
		dfs2(cur);
	}
	else {
		ok[E[cur][0]]=-1;
		dfs(E[cur][1]);
		dfs(E[cur][2]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>X[i];
		top[i]=i;
	}
	FOR(i,M) {
		cin>>A[i]>>B[i]>>Y[i];
		A[i]--;
		B[i]--;
		P[i]={Y[i],i};
	}
	
	sort(P,P+M);
	int cur=N;
	FOR(i,M) {
		x=P[i].second;
		int a=top[uf[A[x]]];
		int b=top[uf[B[x]]];
		if(a!=b) {
			E[cur]={x,a,b};
			X[cur]=X[a]+X[b];
			uf(A[x],B[x]);
			top[uf[A[x]]]=cur;
			cur++;
		}
	}
	
	dfs(cur-1);
	uf.reinit();
	
	int ret=0;
	FOR(i,M) {
		x=P[i].second;
		int a=uf[A[x]];
		int b=uf[B[x]];
		if(ok[x]==1) {
			X[a]=X[b]=X[a]+X[b];
			uf(a,b);
		}
		else if(ok[x]==-1) {
			ret++;
		}
	}
	FOR(i,M) {
		x=P[i].second;
		int a=uf[A[x]];
		if(ok[x]==0 && Y[x]>X[a]) {
			ret++;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

Union-Findによる連結を二分木で表現するテク、以前どこかで使ったのに忘れていた。
これは反省だ…。