BZOJ2125 最短路 【仙人掌+Tarjan+LCA】

tonyfang posted @ 2016年9月30日 21:49 in BZOJ with tags C++ OI , 1280 阅读

【题目大意】多组询问仙人掌上两个点的最短路

【题解】缩点,破环,仙人掌变成树,求LCA。

 

# include <stdio.h>
# include <vector>
# include <map> 
# include <string.h>
using namespace std;

int n, m;
inline int abs(int x) {return x>0?x:-x;} 

int head[300010], next[300010], to[300010], tot=0; 
int scc=0, dfn[300010], low[300010], DFN=0; 
vector<int> s[300010], son[300010]; 
int st[300010], stn=0; 
int fa[500010][16], dep[500010], size[500010];
map<int,int> d[300010], f[300010]; 
int D[300010]; 
inline void add(int u, int v, int tw) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	if(f[u].find(v)==f[u].end()) 
		f[u][v]=tw;
	else f[u][v]=min(f[u][v], tw); 
}
inline int getdep(int x) {
	if(fa[x][0]==0) dep[x]=1;
	if(dep[x]) return dep[x]; 
	return dep[x]=getdep(fa[x][0])+1;
}
	 
inline void init() {
	memset(dep, 0, sizeof(dep)); 
	for (int i=1; i<=15; ++i) {
		for (int j=1; j<=scc; ++j) fa[j][i] = fa[fa[j][i-1]][i-1];
		for (int j=n+1; j<=n*2; ++j) fa[j][i] = fa[fa[j][i-1]][i-1];
	}
	for (int i=1; i<=scc; ++i) getdep(i);
	for (int i=n+1; i<=n*2; ++i) getdep(i);
} 
int tx, ty;
inline int lca(int x,int y)   {  
	if(dep[x]<dep[y]) swap(x,y); 
    for(int j=15; j>=0; --j)  
    	if(dep[fa[x][j]]>=dep[y]) x=fa[x][j]; 
    if(x==y) return x;
	for (int j=15; j>=0; --j) 
		if(fa[x][j] != fa[y][j]) x=fa[x][j], y=fa[y][j];
	tx=x,ty=y;
	return fa[x][0];
}
inline void tarjan(int x) {
	low[x]=dfn[x]=++DFN;
	st[++stn]=x;
	for (int i=head[x]; i; i=next[i]) {
		if(dfn[to[i]] != 0) {
			low[x] = min(low[x], dfn[to[i]]);
		} else {
			tarjan(to[i]);
			if(low[to[i]] == dfn[x]) {
				++scc;
				son[x].push_back(scc); 
				s[scc].push_back(x); 
				fa[scc][0]=n+x; 
				int t;
				do {
					t=st[stn--];
					s[scc].push_back(t); 
					fa[n+t][0]=scc; 
				} while(t != to[i]); 
			}
			low[x] = min(low[x], low[to[i]]);
		}
	}
}
inline void pre(int x) {
 	stn=0;
 	for (int i=0,sz=s[x].size(); i<sz; ++i) st[++stn]=s[x][i];
	st[++stn]=s[x][0];
	for (int i=1; i<stn; ++i) {
		size[x] += f[st[i]][st[i+1]];
		if(i!=stn-1) d[x][st[i+1]]=d[x][st[i]]+f[st[i]][st[i+1]]; 
	}
	int s1=2, t=stn-1;
	while(s1<=t) {
		if(D[st[s1-1]]+f[st[s1-1]][st[s1]]<D[st[t+1]]+f[st[t+1]][st[t]]) { 
			D[st[s1]]=D[st[s1-1]]+f[st[s1-1]][st[s1]];
			++s1;
		} else {
		 	D[st[t]]=D[st[t+1]]+f[st[t+1]][st[t]]; 
		 	--t;
		}
	}
	for (int i=1,sz=s[x].size(); i<sz; ++i)	for (int j=0, szt=son[s[x][i]].size(); j<szt; ++j) pre(son[s[x][i]][j]);
}
		 
int main() {
	scanf("%d%d", &n, &m);	int T;scanf("%d", &T); 
	for (int i=1, u, v, tw; i<=m; ++i) {
		 scanf("%d%d%d", &u, &v, &tw);
		 add(u, v, tw);
		 add(v, u, tw); 
	}
	tarjan(1); init(); 
	for (int j=0,sz=son[1].size();j<sz; ++j) pre(son[1][j]);

	while(T--) {
		int x, y;
		scanf("%d%d", &x, &y);
		int LCA=lca(n+x,n+y);
		if(LCA>n) printf("%d\n", D[x]+D[y]-2*D[LCA-n]); 
		else {
			int ans = D[x]+D[y]-D[tx-n]-D[ty-n];
			int tmp = abs(d[LCA][tx-n]-d[LCA][ty-n]);
			ans+=min(tmp, size[LCA]-tmp);
			printf("%d\n", ans);
		}
	}
	return 0;
}
Sevarth Mahakosh Pay 说:
2022年10月28日 18:06

Maharashtra state government works with a digital website portal to cater to its public sector employees. The government has created an official portal containing all salary-wise details. It’s a self-service portal where employees can access payment information and download their Payslip and other employment-related information. Sevarth Mahakosh Payment Slip The Sevarth facility is a portal developed by the government for online services to the government employees and pensioners.

pavzi.com 说:
2024年1月06日 16:57

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter