kmjp's blog

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

第二回日本最強プログラマー学生選手権 : H - Shipping

その他コンテスト

割と実装が面倒なタイプの問題。
https://atcoder.jp/contests/jsc2021/tasks/jsc2021_h

問題

N点N辺の連結無向グラフが与えられる。
また、各辺にはコストが設定されている。

ここで 、Q個の頂点対が指定される。
辺のうちいくつかを残し、指定された頂点対が連結になるようにしたい。
残す辺の総コストの最小値を求めよ。

解法

N点N辺なので、このグラフはサイクルに(サイクル上の点を根とする)根付き木が複数ぶら下がった形となる。
頂点対のうち、同じ木に属する頂点対に対しては、パスは一意に決まるのでそのパス上の辺は残すことにしよう。
このコストはLCAを使えばO(Q+NlogN)で算出できる。

異なる木に属する頂点対については、それぞれの属する木の根までのパスは残さなければならない。
あとは考えるべきは、サイクル上でいくつかの根の対同士が連結となるよう辺を残すことである。
その際、サイクルのままだと、根の対同士を連結するのにサイクルをどちら周りする辺を残すかで選択肢が残り扱いづらい。

この際、少なくとも1つは残さない辺があっても、根の対同士の連結性を保つことができる。
そこで残さない辺を総当たりしよう。
残さない辺を1つ定めると、各根の対の連結性を保つために残すべき辺が一意に定まる。
これは複数のパスの和集合となるので、SegTreeを使ってそのような和集合のコストの総和を数え上げよう。

int N,M;
vector<pair<int,int>> E[202020];
vector<int> TE;
int P[21][200005],D[200005];
int inloop[202020];
int G[202020];
int add[202020];
ll L[402020];
ll LS[402020];
vector<int> span[404040];

template<int NV> class SegTree_3 {
public:
	vector<int> add, mic;
	vector<ll> mis;
	SegTree_3(){
		add.resize(NV*2,0); mic.resize(NV*2,0); mis.resize(NV*2);
	};
	
	ll getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 0;
		x=max(l,x);
		y=min(r,y);
		
		if(add[k]) {
			return LS[y]-LS[x];
		}
		else {
			if(x<=l && r<=y) return mis[k];
			return getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1);
		}
	}
	
	void update(int x,int y, int v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		x=max(l,x);
		y=min(r,y);
		if(x<=l && r<=y) {
			add[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
		if(add[k]>0) mis[k]=LS[r]-LS[l];
		else mis[k]=mis[2*k]+mis[2*k+1];
	}
};
SegTree_3<1<<19> st;
ll ret_in_tree;

int dfs(int cur) {
	if(cur==TE[1]) inloop[cur]=1;
	
	FORR(e,E[cur]) if(e.first!=P[0][cur]) D[e.first]=D[cur]+1, P[0][e.first]=cur, inloop[cur]|=dfs(e.first);
	return inloop[cur];
}
int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void dfs2(int cur,int pre,int id) {
	G[cur]=id;
	FORR(e,E[cur]) {
		if(e.first!=pre&&inloop[e.first]==0) dfs2(e.first,cur,id);
		if(inloop[cur]&&inloop[e.first]&&D[cur]<D[e.first]) L[D[cur]]=e.second;
	}
}
void dfs3(int cur,int pre) {
	FORR(e,E[cur]) {
		if(e.first!=pre&&inloop[e.first]==0) dfs3(e.first,cur);
	}
	FORR(e,E[cur]) if(e.first==pre) {
		add[e.first]+=add[cur];
		if(add[cur]) ret_in_tree+=e.second;
	}
}

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>>x>>k;
		if(uf[i]==uf[x-1]) {
			TE={x-1,i,k};
		}
		else {
			E[i].push_back({x-1,k});
			E[x-1].push_back({i,k});
			uf(i,x-1);
		}
	}
	P[0][TE[0]]=TE[0];
	dfs(TE[0]);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	FOR(i,N) if(inloop[i]) dfs2(i,i,i);
	int TL=D[TE[1]]+1;
	L[TL-1]=TE[2];
	
	FOR(i,2*TL) LS[i+1]=LS[i]+L[i%TL];
	
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		add[x]++;
		add[y]++;
		if(G[x]==G[y]) {
			k=lca(x,y);
			add[k]-=2;
		}
		else {
			add[G[x]]--;
			add[G[y]]--;
			x=D[G[x]];
			y=D[G[y]];
			span[min(x,y)].push_back(max(x,y));
			st.update(min(x,y),max(x,y),1);
		}
	}
	FOR(i,N) if(inloop[i]) dfs3(i,i);
	
	ll ret=LS[TL];
	FOR(i,TL) {
		ret=min(ret,st.getval(i,i+TL));
		FORR(e,span[i]) {
			st.update(i,e,-1);
			st.update(e,i+TL,1);
			span[e].push_back(i+TL);
		}
		
	}
	
	cout<<(ret+ret_in_tree)<<endl;
	
}

まとめ

似たようなの昔Codeforcesで見たな。