這個(gè)東西我自己也不知道怎么精簡，所以直接貼原題題面了。

題意

Bessie 位于一個(gè)由 \(N\) 個(gè)編號為 \(1\dots N\) 的結(jié)點(diǎn)以及 \(2N\) 個(gè)編號為 \(1\cdots 2N\) 的傳送門所組成的網(wǎng)絡(luò)中。每個(gè)傳送門連接兩個(gè)不同的結(jié)點(diǎn) \(u\) 和 \(v\)（\(u≠v\)）。可能有多個(gè)傳送門連接同一對結(jié)點(diǎn)。

每個(gè)結(jié)點(diǎn) \(v\) 與四個(gè)不同的傳送門相連。與 \(v\) 相連的傳送門列表由 \(p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]\) 給出。

你的當(dāng)前位置可以用有序?qū)Γó?dāng)前結(jié)點(diǎn)，當(dāng)前傳送門）表示；即一個(gè)有序?qū)?\((v,p_{v,i})\)
，其中 \(1\le v\le N\) 以及 \(1\le i\le 4\)。你可以使用以下任一操作來改變你的當(dāng)前位置：

• 1. 由穿過當(dāng)前傳送門來改變當(dāng)前結(jié)點(diǎn)。
• 2. 改變當(dāng)前傳送門。在每一個(gè)結(jié)點(diǎn)上，列表的前兩個(gè)傳送門是配對的，后兩個(gè)傳送門也是配對的。也就是說，如果你的當(dāng)前位置是 \((v,p_{v,2})\)，你可以轉(zhuǎn)而使用傳送門 \((v,p_{v,1})\)，反之亦然。類似地，如果你的當(dāng)前位置是 \((v,p_{v,3})\)，你可以轉(zhuǎn)而使用傳送門 \((v,p_{v,4})\)，反之亦然。沒有其他改變傳送門的方式（例如，你不能從傳送門 \(p_{v,2}\) 轉(zhuǎn)去傳送門 \(p_{v,4}\) ）。

總共有 \(4N\) 個(gè)不同的位置。不幸的是，并不一定每一個(gè)位置都可以從另外的每一個(gè)位置經(jīng)過一系列操作而到達(dá)。所以，以 \(c_v\) 哞尼的代價(jià)，你可以以任意順序重新排列與 \(v\) 相鄰的傳送門列表。在此之后，列表中的前兩個(gè)傳送門互相配對，同時(shí)后兩個(gè)傳送門也互相配對。

例如，如果你將與 \(v\) 相鄰的傳送門以 \([p_{v,3},p_{v,1},p_{v,2},p_{v,4}]\) 的順序重新排列，這意味著如果你位于結(jié)點(diǎn) \(v\) ，

• 如果你當(dāng)前位于傳送門 \(p_{v,1}\) ，你可以轉(zhuǎn)而使用傳送門 \(p_{v,3}\)，反之亦然。
• 如果你當(dāng)前位于傳送門 \(p_{v,2}\) ，你可以轉(zhuǎn)而使用傳送門 \(p_{v,4}\)，反之亦然。
  你不再能夠從傳送門 \(p_{v,1}\)
  轉(zhuǎn)至傳送門 \(p_{v,2}\)，或從傳送門 \(p_{v,3}\) 轉(zhuǎn)至 \(p_{v,4}\) ，反之亦然。

計(jì)算修改這一網(wǎng)絡(luò)使得每一個(gè)位置都可以從另外的每一個(gè)位置到達(dá)所需要花費(fèi)的哞尼的最小數(shù)量。輸入保證存在至少一種修改網(wǎng)絡(luò)的合法方式。

輸入格式

輸入的第一行包含 \(N\)。

以下 \(N\) 行每行描述一個(gè)結(jié)點(diǎn)。第 \(v+1\) 行包含五個(gè)空格分隔的整數(shù) \(c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}\)。

輸入保證對于每一個(gè) \(v\) ，\(p_{v,1},p_{v,2},p_{v,3},p_{v,4}\) 各不相同，且每個(gè)傳送門出現(xiàn)在恰好兩個(gè)結(jié)點(diǎn)的鄰接表中。

輸出格式

輸出一行，包含修改這一網(wǎng)絡(luò)使得每一個(gè)位置都可以從另外的每一個(gè)位置到達(dá)所需要花費(fèi)的哞尼的最小數(shù)量。

輸入輸出樣例 #1

輸入 #1

5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5

輸出 #1

13

說明/提示

樣例解釋

重新排列結(jié)點(diǎn) \(1\) 和 \(4\) 的鄰接表就已足夠。這需要總計(jì) \(c_1+c_4=13\) 哞尼。我們可以使 \(p_1=[1,9,4,8]\) 以及 \(p_4=[7,4,6,3]\)。

數(shù)據(jù)范圍與約定

\(2\le N\le 10^5\)，\(1\le c_v\le 10^3\)。

做法

這個(gè)東西第一次看固然是懵的，感覺就是很亂，不過細(xì)細(xì)理一理會明白它實(shí)際上在做什么。

明顯我們在試圖把所有點(diǎn)放到一個(gè)聯(lián)通快里邊，像是最小生成樹？

注意我們這里表示的點(diǎn)不是所謂的結(jié)點(diǎn)，而是傳送門。

我們本來是兩個(gè)節(jié)點(diǎn)的每兩個(gè)傳送門對應(yīng)連接的，它們之間也有邊，分成了兩塊，這樣顯然各個(gè)傳送門會不聯(lián)通，我們所作的操作實(shí)際上就是把這一堆合并起來。

這下就完了，直接最小生成樹做就行。

代碼↓

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
int father[MN], n;
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
void merge(int x, int y){
	x=find(x), y=find(y);
	if(x==y) return;
	father[x]=y; return;
}
struct Node{
	int pos, val;
	bool operator <(const Node &o)const{
		return val<o.val;
	}
}node[MN];
int G[MN][5], ans=0;
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=0; i<MN; ++i) father[i]=i;
	for(int i=1; i<=n; ++i){
		node[i].pos=i; cin>>node[i].val;
		cin>>G[i][1]>>G[i][2]>>G[i][3]>>G[i][4];
		merge(G[i][1],G[i][2]);
		merge(G[i][3],G[i][4]);
	}
	sort(node+1,node+n+1);
	for(int i=1; i<=n; ++i){
		int pos=node[i].pos;
		int u=find(G[pos][1]), v=find(G[pos][3]);
		if(u==v) continue;
		merge(u,v); ans+=node[i].val; 
	}
	cout<<ans<<'\n';
	return 0;
}