【8.21模拟賽T2.7221】[USACO21OPEN] Portals G【kruskal】

題目連結：https://www.luogu.com.cn/problem/P7528，https://gmoj.net/senior/#main/show/7221

分析

這題題意真是有點點玄啊。

但是我看了題意分析之後就感覺不是特别難。

一開始（1,2）(3.4)是配對的，我們需要改變傳送門的位置使所有的點變成一個連通塊。很顯然如果存在兩個環， 我們需要将它變成一個環，那麼就可以達到目的了。

上代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,d,ans;
int p[1000005][5],fa[2000005];

struct node
{
	int s,id;
}a[1000001];

int cmp(node l,node r)
{
	return l.s<r.s;
}

int father(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=father(fa[x]);
}

int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)
	{
		fa[i]=i;
	} 
	for(int i=1;i<=n;i++)
	{
	    scanf("%d",&a[i].s);
		a[i].id=i;
		scanf("%d%d%d%d",&p[i][1],&p[i][2],&p[i][3],&p[i][4]);
		fa[father(p[i][1])]=father(p[i][2]);//這裡初始化多個環 
		fa[father(p[i][3])]=father(p[i][4]);
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)//Kruskal,使所有環聯通
	{
		int t=a[i].id;
		int fx=father(p[t][1]);
		int fy=father(p[t][3]);
		if(fx!=fy)
		{
			fa[fx]=fy;
			ans+=a[i].s;
		} 
	}
	cout<<ans;
	return 0;
}