kmjp's blog

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

第六回 アルゴリズム実技検定 : O - 最短距離クエリ

割とすんなり。
https://atcoder.jp/contests/past202104-open/tasks/past202104_o

問題

N点M辺の連結無向グラフが与えられる。
なお、M≦N+10である。

クエリとして2点が与えられるので、その間の最短距離を求めよ。

解法

Mが小さいことを利用する。
まず適当な全域木を求め、それらをLCAで高速に距離計算できるようにしておく。
ここで、全域木に使わなかった(M-(N-1))辺の端点について、そこから各点までの最短距離を求めておこう。

各クエリの処理は、上記各端点ついて、その端点を経由した場合を総当たりしつつ、端点を通らない場合と比較して最小値を答えよう。

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<101010> uf;
int N,M;
vector<int> E[101010],E2[101010];
vector<int> cand;
int DD[101010][21];

int P[21][200005],D[200005];

void dfs(int cur) {
	FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e);
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return 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 solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(uf[x]!=uf[y]) {
			E[x].push_back(y);
			E[y].push_back(x);
			E2[x].push_back(y);
			E2[y].push_back(x);
			uf(x,y);
		}
		else {
			E2[x].push_back(y);
			E2[y].push_back(x);
			cand.push_back(x);
		}
	}
	FOR(i,cand.size()) {
		x=cand[i];
		FOR(j,N) DD[j][i]=1<<30;
		queue<int> Q;
		DD[x][i]=0;
		Q.push(x);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			FORR(e,E2[cur]) if(DD[e][i]>DD[cur][i]+1) {
				DD[e][i]=DD[cur][i]+1;
				Q.push(e);
			}
		}
	}
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		int ret=1<<20;
		FOR(i,cand.size()) ret=min(ret,DD[x][i]+DD[y][i]);
		int lc=lca(x,y);
		ret=min(ret,D[x]+D[y]-2*D[lc]);
		cout<<ret<<endl;
	}

	
	
}

まとめ

辺に距離がついてもよいかと思ったけど、この問題では距離無しだった。