社区讨论
请问结构体嵌套结构体的cmp函数怎么办
学术版参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi7dufg4
- 此快照首次捕获于
- 2025/11/20 20:03 4 个月前
- 此快照最后确认于
- 2025/11/20 20:03 4 个月前
这个代码我知道有很多bug,
但是我想问一下那个cmp函数过不了编译,怎么改那个cmp函数
CPP但是我想问一下那个cmp函数过不了编译,怎么改那个cmp函数
#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 条回复,欢迎继续交流。
正在加载回复...