求条,莓果样例
查看原帖
求条,莓果样例
753640
封禁用户楼主2024/5/3 19:33
#include<bits/stdc++.h>
#define sd std::
//#define int long long
#define inf 0x3f3f3f3f
#define linf 1e18
#define il inline
#define db double
#define ldb long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define f(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
#define umap(x,y) sd unordered_map<x,y>
#define pque(x) sd priority_queue<x>
#define X first
#define Y second
#define kg putchar(' ')
#define Fr(a) for(auto it:a)
#define dbg(x) sd cout<<#x<<": "<<x<<sd endl
il int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
il void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
il void put(int x){print(x);putchar('\n');}
il void printk(int x){print(x);kg;}
const int N=1e5+10,logN=25;
int n,m;
struct node
{
	int nex;
	int to;
}a[N<<1];
int tot,head[N];
struct kruskal_tree
{	
	void add(int u,int v)
	{
		a[++tot].nex=head[u];
		head[u]=tot;
		a[tot].to=v;
	}
	int fa[N];//并查集 
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	il void merge(int x,int y){fa[x]=y;}
	il void init_fa()
	{
		F(i,1,N-1) fa[i]=i;
	}
	struct edge
	{
		int u,v,w;
		bool operator<(const edge&b)
		{
			return w<b.w;
		}
	}e[N];
	int val[N<<1],cnt;
	void built()//建树 
	{
		sd sort(e+1,e+1+m);
		init_fa();
		F(i,1,m)
		{
			int x=find(e[i].u),y=find(e[i].v);
			if(x==y) continue;
			val[++cnt]=e[i].w;
			fa[x]=fa[y]=fa[cnt]=cnt;
			add(cnt,x);
			add(cnt,y);
		}
	}
}T;
int dep[N],f[N][logN],vis[N];
void pre(int u,int fa)
{
	vis[u]=1;
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	F(i,0,20) f[u][i+1]=f[f[u][i]][i];
	for(int i=head[u];i;i=a[i].nex)
	{
		int v=a[i].to;
		if(vis[v]) continue;
		pre(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) sd swap(x,y);
	f(i,20,0)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
	}
	f(i,20,0)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int q;
il void solve()
{
	n=read(),m=read();T.cnt=n;
	F(i,1,m) T.e[i].u=read(),T.e[i].v=read(),T.e[i].w=read();
	T.built();
	pre(1,0);
	q=read();
	F(i,1,q)
	{
		int u=read(),v=read();
		if(T.find(u)!=T.find(v)) puts("-1");
		else put(T.val[lca(u,v)]);
	}
}
int main()
{
    int T=1;
//    T=read();
    while(T--) solve();
    return 0;
}
2024/5/3 19:33
加载中...