// 最小生成树 kruskal 算法 O(m*logm)
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,ans;
int c[N],p[N][5];
int fa[2*N];
pair<int,int> v[N];

int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merg(int x,int y){
  fa[find(x)]=find(y);
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=2*n;i++) fa[i]=i; //传送门编号
  for(int i=1;i<=n;i++){
    scanf("%d%d%d%d%d",&c[i],&p[i][1],&p[i][2],&p[i][3],&p[i][4]);
    merg(p[i][1],p[i][2]); 
    merg(p[i][3],p[i][4]); //合并两个传送门
  }
  
  for(int i=1;i<=n;i++) v[i]={c[i],i}; //绑定代价和点编号
  sort(v+1,v+n+1);
  for(int i=1;i<=n;i++){
    auto [c,j]=v[i];
    int x=find(p[j][1]),y=find(p[j][3]);
    if(x!=y){
      fa[x]=y;
      ans+=c;
    }
  }
  printf("%d",ans);
}

将传送门进行连边，最后会形成一些联通块。

目标是将这些联通块都连接在一起。

思考交换操作的意义，发现交换操作会将两个环连在一起，即将两个环所在的联通块连在一起。

那我们就像 kruskal 最小生成树算法一样，将联通块合并在一起即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+5;
int T=1,n,ans;
int fa[maxn],a[maxn][4];
int get_fa(int x)
{
	return fa[x]==x?x:fa[x]=get_fa(fa[x]);
}
void ins(int u,int v)
{
	int uu=get_fa(u),vv=get_fa(v);
	fa[uu]=vv;
}
struct node
{
	int id,w;
	bool operator < (const node &x) const
	{
		return w<x.w;
	}
};
node c[maxn];
void solve()
{
	scanf("%lld",&n);
	for(int i=1;i<=n*2;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld%lld",&c[i].w,&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
		ins(a[i][0],a[i][1]);ins(a[i][2],a[i][3]);
		c[i].id=i;
	}
	sort(c+1,c+n+1);
	for(int i=1;i<=n;i++){
		int id=c[i].id;
		int uu=get_fa(a[id][0]);
		int vv=get_fa(a[id][2]);
		if(uu!=vv){
			fa[uu]=vv;
			ans+=c[i].w;
		}
	}
	printf("%lld\n", ans);
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
//	scanf("%lld",&T);
	while(T--){
		solve();
	}
	return 0;
}
//dyyyyds