CPSCO2019 Session2 : G - MSTX

方針立てるのにちょっと手間取った。
https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_g

問題

　
N頂点M辺の連結無向グラフが与えられる。
各辺には重さが設定されている。しかし一部の辺の重さは変数Xとなっている。

以下のクエリに順次答えよ。

変数Xが設定された辺の重さを、一律で指定した値Aにしたとき、最小全域木の重さはいくつか。

解法

まず、元の辺を以下分類する。

辺の重さが変数Xで
1. Xが何であれ最小全域木に含まれる。
2. Xの値によっては最小全域木に含まれる。
3. 最小全域木には含まれない。
辺の重さが定数で
1. Xが何であれ最小全域木に含まれる。
2. Xの値によっては最小全域木に含まれる。
3. 最小全域木には含まれない。

これらは、以下の通りクラスカル法を2回行えば分類できる。

先に重さがXの辺のみ処理し、その後重さが定数の辺を処理する
先に重さが定数の辺のみ処理し、その後重さが変数Xの辺を処理する

あとは各クエリの処理である。

1.1に該当する辺は、必ず最小全域木に含まれるので、(X×辺の数)分だけ解に加算される
2.1に該当する辺は、必ず最小全域木に含まれるので、それぞれの重さの分だけ解に加算される
1.2,2,2に該当する辺は、Xの重さしだいで何本どちらが採用されるか決まる。重さA以下の辺は後者から、残りは前者から利用されるので、2.2の辺の重さをソートしておけば後者から利用される辺の本数が高速に求められる。

int N,M;
int U[50505],V[50505],C[50505],W[50505];
vector<pair<int,int>> E;
vector<int> F;
int need[50505];
int Q;
ll A;

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<50505> uf1,uf2;
vector<int> cand;
vector<ll> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,M) {
		cin>>U[i]>>V[i]>>C[i];
		U[i]--;
		V[i]--;
		if(C[i]==0) {
			cin>>W[i];
			E.push_back({W[i],i});
		}
		else {
			cin>>s;
			F.push_back(i);
		}
	}
	
	sort(ALL(E));
	FORR(f,F) uf2(U[f],V[f]);
	
	ll sum=0;
	FORR(e,E) {
		if(uf1[U[e.second]]!=uf1[V[e.second]]) {
			need[e.second]|=1;
			uf1(U[e.second],V[e.second]);
		}
		if(uf2[U[e.second]]!=uf2[V[e.second]]) {
			need[e.second]|=2;
			uf2(U[e.second],V[e.second]);
			sum+=W[e.second];
		}
	}
	int nx=0;
	FORR(f,F) if(uf1[U[f]]!=uf1[V[f]]) {
		nx++;
		uf1(U[f],V[f]);
	}
	
	FOR(i,M) if(need[i]==1) cand.push_back(W[i]);
	sort(ALL(cand));
	S.push_back(0);
	FORR(c,cand) S.push_back(S.back()+c);
	
	cin>>Q;
	while(Q--) {
		cin>>A;
		x=lower_bound(ALL(cand),A)-cand.begin();
		ll ret=sum+nx*A+S[x]+(cand.size()-x)*A;
		cout<<ret<<endl;
	}
	
	
}

まとめ

500ptよりは難しそうだけど、700ptぐらい？

kmjp's blog

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

CPSCO2019 Session2 : G - MSTX

問題

解法

まとめ