已 AC 但是疑惑
  • 板块P2700 逐个击破
  • 楼主linch吃瓜猫
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/7/23 20:37
  • 上次更新2025/7/24 10:26:19
查看原帖
已 AC 但是疑惑
737242
linch吃瓜猫楼主2025/7/23 20:37

由于 QQ 登不上,所以没法在答疑群里提问。

RT,按照第一篇题解的思路,想知道为什么在判断是否连接时要判断一条边的两个节点的祖先是否都是敌人节点或和敌人节点相连,即被标记的节点。而不是这两个节点本身?(在代码中已做标记)

附:代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long n,k,sum;
struct edge{
    long long u,v,w;
}e[maxn];
bool cmp(edge xx,edge yy){
    return xx.w>yy.w;
}
int f[maxn];
bool vis[maxn];
int find(int x){
    return f[x]==x ? x : find(f[x]);
}
int main(){
	cin>>n>>k;
    for(int i=0;i<=n;i++) f[i]=i;
    for(int i=1;i<=k;i++){
        long long x;
        cin>>x;
        vis[x]=true;
    }
    for(int i=1;i<n;i++){
        long long u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
        sum+=w;
    }
    sort(e+1,e+n,cmp);
    for(int i=1;i<n;i++){
        int x=find(e[i].u),y=find(e[i].v);//指这一行
        if(x==y) continue;//指这一行
        if(vis[x] && vis[y]) continue;//指这一行
        if(vis[x] || vis[y]) vis[x]=true,vis[y]=true;//指这一行
        sum-=e[i].w;
        f[find(x)]=find(y);
    }
    cout<<sum<<"\n";
	return 0;
}
2025/7/23 20:37
加载中...