夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

Kruskal重构树复习

2020-06-11 9 min read

From 2020省选前复习

首先这个算法的核心是kruskal算法,就是在其上加入了一些新元素使之更优秀了

我们还是边权排序去做最小生成树,但是这次我们在连树边的时候,先建立一个新点

新点的权值是边权值,然后新点成为原来的边的起点终点的父亲,一直做下去就好了qwq

这个树有什么性质呢?

  1. 二叉树
  2. x,y的LCA代表的点权一定是他们路径上的极值
  3. 如果

然后上例题

T1货车运输

两点间路径最大的最小值

直接重构树,然后是从大到小排序即可

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
using std::sort;
const int MAXN = 2e5 + 7;
int n, m;
struct rec {
	int x, y, w;
	bool operator<(const rec &x)const {
		return w > x.w;
	}
} e[MAXN];
int f[MAXN], a[MAXN], fa[MAXN];
int ccnt;
int home[MAXN], nxt[MAXN], to[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline int getf(int x) {
	return f[x] == x ? x : f[x] = getf(f[x]);
}

inline void builtT() {
	sort(e + 1, e + m + 1);
	for(int i = 1; i <= m; ++i) {
		int u = e[i].x;
		int v = e[i].y;
		if(getf(u) == getf(v))continue;
		u = getf(u);
		v = getf(v);
		++n;
		f[n] = n;
		ct(n, u);
		ct(n, v);
		a[n] = e[i].w;
		f[u] = n;
		f[v] = n;
	}
	return;
}

int siz[MAXN], dep[MAXN], son[MAXN];
inline void dfs1(int u, int F) {
	fa[u] = F;
	siz[u] = 1;
	int maxson = -1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > maxson) {
			maxson = siz[v];
			son[u] = v;
		}
	}
	return ;
}

int top[MAXN];
inline void dfs2(int u, int topf) {
	top[u] = topf;
	if(!son[u])return;
	dfs2(son[u], topf);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == son[u] || v == fa[u])continue;
		dfs2(v, v);
	}
	return ;
}

inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	return x;
}

inline void init() {
	dfs1(n, 0);
	dfs2(n, n); //n is root
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
	}
	for(int i = 1; i <= n; ++i)f[i] = i;
	builtT();
	init();
	int q;
	scanf("%d", &q);
	for(int i = 1, x, y; i <= q; ++i) {
		scanf("%d%d", &x, &y);
		if(getf(x) != getf(y)) {
			puts("-1");
			continue;
		}
		int anc = LCA(x, y);
		printf("%d\n", a[anc]);
	}
	return 0;
}

T2NOI2018归程

考虑从点1跑一个最短路,得到每个点到n的最短路信息

问题变成只走海拔大于x的边能走到的点中到1的最短路最小是什么

考虑按照海拔重构树,然后海拔是从大到小排序的,那么对于一个点,他一定有某个祖先的父亲是权值小于等于x的,倍增找到这个满足的点

然后这个点的子树中最短路最小的就是答案qwq

code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define mkp(x,y) (make_pair(x,y))
#define se second
const int MAXN=1e6+7;
const int inf=2e9+7;
using namespace std;
int n,m,q,k,s;
struct rec {
	int u,v,l,h;
	bool operator<(const rec &x)const {
		return h>x.h;
	}
} e[MAXN];
struct edge {
	int to,nxt,h;
} E[MAXN];

int f[MAXN];
inline int getf(int u) {
	return f[u]==u?u:f[u]=getf(f[u]);
}

int home[MAXN],nxt[MAXN],to[MAXN],ccnt,len[MAXN],first[MAXN],cnt;
inline void ct(int x,int y,int w) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
	len[ccnt]=w;
}
inline void ct2(int x,int y) {
	cnt++;
	E[cnt].nxt=first[x];
	first[x]=cnt;
	E[cnt].to=y;
}

priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > que;
int dis[MAXN],vis[MAXN];

inline void dijkstra() {
	int s=1;
	while(!que.empty())que.pop();
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	que.push(mkp(0,s));
	while(!que.empty()) {
		int u=que.top().se;
		que.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			if(dis[u]+len[i]<dis[v]) {
				dis[v]=dis[u]+len[i];
				que.push(mkp(dis[v],v));
			}
		}
	}
	return ;
}

int fa[MAXN][20];
int ans[MAXN],a[MAXN];
inline void dfs(int u,int F) {
	ans[u]=dis[u];
//	a[u]=h;
	fa[u][0]=F;
	for(int i=first[u]; i; i=E[i].nxt) {
		int v=E[i].to;
		if(v==F)continue;
		dfs(v,u);//qwq
		ans[u]=min(ans[u],ans[v]);
	}
//	printf("%d %d %d\n",u,ans[u],a[u]);

	return ;
}

inline void solve() {
	dijkstra();
//	for(int i=1; i<=n; ++i)printf("%d ",dis[i]);
//	puts("");
	sort(e+1,e+m+1);
	for(int i=1; i<=n; ++i)f[i]=i,a[i]=inf;
	for(int i=1; i<=m; ++i) {
		int u=e[i].u;
		int v=e[i].v;
		int h=e[i].h;
		int l=e[i].l;//qwq
//		printf("%d %d\n",u,v);

		if(getf(u)==getf(v))continue;

		u=getf(u);
		v=getf(v);
		++n;
		a[n]=h;
		f[n]=n;
		f[u]=n;
		f[v]=n;
		ct2(n,u);
		ct2(n,v);
	}
	dfs(n,0);//init 子树最大值,以及倍增
	for(int i=1; i<=18; ++i) {
		for(int j=1; j<=n; ++j) {
			fa[j][i]=fa[fa[j][i-1]][i-1];//qwq
		}
	}
	return ;
}

inline void init() {
	memset(home,0,sizeof(home));
	ccnt=0;
	cnt=0;
	memset(first,0,sizeof(first));
	memset(a,0,sizeof(a));
	a[0]=inf;
}

int main() {
	int T;
	scanf("%d",&T);
	while(T-->0) {
		init();
		scanf("%d%d",&n,&m);
		int tmp=n;
		for(int i=1; i<=m; ++i) {
			scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].h);
			ct(e[i].u,e[i].v,e[i].l);
			ct(e[i].v,e[i].u,e[i].l);
		}
		solve();//build Tree and dijkstra
		scanf("%d%d%d",&q,&k,&s);
		int lst=0;
		for(int i=1,u,p; i<=q; ++i) {
			scanf("%d%d",&u,&p);
			u=(u+k*lst-1)%tmp+1;
			p=(p+k*lst)%(s+1);
//			printf("%d %d??\n",u,p);
			for(int i=17; i>=0; --i) {
				if(fa[u][i]==0)continue;
				if(a[fa[u][i]]>p) {
					u=fa[u][i];
				}
			}
//			printf("%d\n",u);
			lst=ans[u];
			printf("%d\n",lst);
		}
	}
	return 0;
}

完结撒花

Powered by Gridea RSS