社区讨论

请问结构体嵌套结构体的cmp函数怎么办

学术版参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi7dufg4
此快照首次捕获于
2025/11/20 20:03
4 个月前
此快照最后确认于
2025/11/20 20:03
4 个月前
查看原帖
这个代码我知道有很多bug,
但是我想问一下那个cmp函数过不了编译,怎么改那个cmp函数
CPP
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50010;
const int inf = 1e9;
int n,m,q;
int fa[MAXN],deep[MAXN],get[MAXN][20],father[MAXN][20];
struct Graph
{
	int cnt;
	int head[MAXN];
	struct Edge
	{
		int from,to,next,val;
	}e[MAXN<<1];
	inline void add(int u,int v,int w)
	{
		cnt++;
		e[cnt].to=v;
		e[cnt].next=head[u];
		e[cnt].from=u;
		e[cnt].val=w;
	}	
}G1,G2;
inline bool cmp(Edge a,Edge b){return G1.a.val>G1.b.val;}
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<2)+c-'0';c=getchar();}
	return f*x;
}
int Find(int now){return fa[now]<=0?now:fa[now]=Find(fa[now]);}
inline void Merge(int x,int y)
{
	fa[x]+=fa[y];
	fa[y]=x;
}
void dfs(int now,int fa,int dep)
{
	deep[now]=dep;
	for(int i=G2.head[now];i;i=G2.e[i].next){
		if(G2.e[i].to==fa) continue;
		get[G2.e[i].to][0]=G2.e[i].val;
		father[G2.e[i].to][0]=now;
		dfs(G2.e[i].to,now,dep+1);
	}
}
inline void Init()
{
	for(int i=1;i<=n;i++) 
	    if(!deep[i]) dfs(i,-1,1);
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			father[j][i]=father[father[j][i-1]][i-1],
			get[j][i]=min(get[j][i-1],get[father[j][i-1]][i-1]);
} 
inline int lca(int u,int v)
{
	int ans=inf;
	if(deep[u]>deep[v]) swap(u,v);
	for(int i=20;i>=0;i--)
		if(deep[father[v][i]]>=deep[u])
			ans=min(ans,get[v][i]),
			v=father[v][i];
	if(u==v) return ans;
	for(int i=20;i>=0;i--)
		if(father[u][i]!=father[v][i])
			ans=min(ans,min(get[u][i],get[v][i])),
			u=father[u][i],
			v=father[v][i];
	return min(ans,min(get[u][0],get[v][0]));
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		G1.add(u,v,w);
		G1.add(v,u,w);
	}
	sort(G1.e+1,G1.e+G1.cnt+1,cmp);
	for(int i=1;i<=m;i++){
		int fx=Find(e[i].from);
		int fy=Find(e[i].to);
		if(fx==fy) continue;
		Merge(G1.e[i].from,G1.e[i].to);
		G2.add(G1.e[i].from,G1.e[i].to);
	}
	q=read();
	Init();
	for(int i=1;i<=q;i++){
		int u=read(),v=read();
		int fx=Find(u);
		int fy=Find(v);
		if(fx==fy) printf("%d\n",lca(u,v));
		else puts("-1");
	}
}

回复

7 条回复,欢迎继续交流。

正在加载回复...