kmjp's blog

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

Codeforces Global Round 14 : F. Phoenix and Earthquake

ダメダメだった回。
https://codeforces.com/contest/1515/problem/F

問題

N頂点と、M個の辺の候補が与えられる。
各頂点には、アスファルトがA[i]トンある。

ある辺の候補を、実際の辺にする場合、両端の連結成分内のアスファルトの合計がXトン以上なければならない。
またその時、辺を張って連結すると、連結成分のアスファルト量は、連結前の両連結成分のアスファルト量の和からXを引いたものになる。

これらの頂点を木とできるか。できるなら辺を結ぶ例を示せ。

解法

N連結成分に対し、アスファルト総量が(N-1)*X以上なら必ず解がある。
最大量のアスファルトの連結成分に対し、そこにつながる辺を総当たりして、両端のアスファルト量の和がXを超える辺を貪欲に選ぶことを繰り返してよい。

int N,M,X;
ll A[303030];

set<pair<int,int>> E[303030];
int R[303030];
int U[303030],V[303030];

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 num=um) {int i; FOR(i,num) 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<303030> uf;
vector<int> ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>X;
	ll sum=0;
	FOR(i,N) {
		cin>>A[i];
		sum+=A[i];
	}
	if(sum<1LL*(N-1)*X) {
		cout<<"NO"<<endl;
		return;
	}
	
	FOR(i,M) {
		cin>>U[i]>>V[i];
		U[i]--;
		V[i]--;
		if(uf[U[i]]!=uf[V[i]]) {
			uf(U[i],V[i]);
			E[U[i]].insert({V[i],i+1});
			E[V[i]].insert({U[i],i+1});
		}
	}
	
	
	uf.reinit();
	set<pair<ll,int>> S;
	FOR(i,N) S.insert({-A[i],i});

	cout<<"YES"<<endl;
	while(S.size()>1) {
		int cur=uf[S.begin()->second];
		S.erase(S.begin());
		
		int tar=0;
		while(E[cur].size()) {
			tar=uf[E[cur].begin()->first];
			if(cur!=tar) break;
			E[cur].erase(E[cur].begin());
		}
		cout<<E[cur].begin()->second<<endl;
		E[cur].erase(E[cur].begin());
		x=uf(cur,tar);
		y=cur+tar-x;
		S.erase({-A[tar],tar});
		A[cur]=A[tar]=A[cur]+A[tar]-X;
		S.insert({-A[x],x});
		if(E[x].size()<E[y].size()) swap(E[x],E[y]);
		FORR(v,E[y]) E[x].insert(v);
		
	}
}

まとめ

解法は意外にシンプル。