P2245 求调 qwq
  • 板块灌水区
  • 楼主j_steady
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/14 16:25
  • 上次更新2023/10/27 20:22:43
查看原帖
P2245 求调 qwq
559503
j_steady楼主2022/7/14 16:25

为什么dfs卡死了啊啊啊 看了一下午了……

#include <bits/stdc++.h>
#define maxn 200005
#define maxm 300005
using namespace std;
inline int read(){char c=getchar();int f=1;while (c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*f;}
int t,n,m,q,fa[maxn],hd[maxn],cnt,dis[maxn],tot,l[maxn],r[maxn],vis[maxn],ffa[maxn][25],ww[maxn];
struct edge{
	int u,v,w;
}ee[maxm*3];
struct node{
	int v,nxt;
}e[maxm*3];
void init (){
	for(int i=1;i<=n;i++){
		fa[i] = i;
	}
}
void add(int u,int v){
	e[++cnt].v = v;
	e[cnt].nxt = hd[u];
	hd[u] = cnt;
}
int find(int x){
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void join(int x,int y,int w){
	int fx = find(x),fy = find(y);
	fa[fx] == ++t;
	fa[fy] == t;
	add(fx,t);add(t,fx);
	add(fy,t);add(t,fy);
	ww[t] = w;
}
bool judge(int a,int b){
	return (l[a]<=l[b]&&r[a]>=r[b]);
}
void dfs(int x,int y){
	l[x] = ++tot;
	vis[x] = 1;puts("1");
	for(int i=hd[x];i;i=e[i].nxt){
		int v=e[i].v;
		puts("34");
		if(v==y) {
			puts("K");continue;
		}
		ffa[v][0] = x;
		dis[v] = dis[x] + 1;
		dfs(v,x);
	}	              
	r[x] = tot;
}
int lca(int x,int y){
	if(x == y) return x;
	if(dis[x] < dis[y]) swap(x,y);
	for(int i=20;i>=0;i--){
		if(!judge(ffa[x][i],y)) x=ffa[x][i];
	} 
	return ffa[x][0];
}
bool cmp(edge a,edge b){
	return a.w < b.w;
}
int main (){
	n=read(),m=read();
	init();
	for(int i=1;i<=m;i++){
		ee[i].u=read(),ee[i].v = read(), ee[i].w = read();
	}
	sort(ee+1,ee+m+1,cmp);
	t=n;
	for(int i=1;i<=m;i++){
		int fu=find(ee[i].u),fv=find(ee[i].v);
		if(fu!=fv){
			join(ee[i].u,ee[i].v,ee[i].w);
		}
	}
	for(int i=1;i<=t;i++){
		 if(!vis[i] && find(i) == i) {
			dfs(i,0);ffa[i][0] = i;
		 }
	}//??
	n=t;
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n;j++){
			ffa[i][j] = ffa[ffa[i][j-1]][j-1];
		}
	}
		
	q=read();
	while (q--) {
		int x=read(),y=read();
		if(find(x) != find(y)) puts("-1");
		else printf ("%d\n",ww[lca(x,y)]);
	}
	return 0;
}
2022/7/14 16:25
加载中...