P7528 [USACO21OPEN] Portals G

luogu題目傳送門

題目描述

Bessie 位于一個由 $N$ 個編號為 $1\dots N$ 的結點以及 $2N$ 個編號為 $1?2N$ 的傳送門所組成的網絡中。每個傳送門連接兩個不同的結點 $u$ 和 $v$（$u\ne v$）。可能有多個傳送門連接同一對結點。

每個結點 $v$ 與四個不同的傳送門相連。與 $v$ 相連的傳送門列表由 $p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]$ 給出。

你的當前位置可以用有序對（當前結點，當前傳送門）表示；即一個有序對 $(v,p_{v,i})$
，其中 $1\le v\le N$ 以及 $1\le i\le 4$。你可以使用以下任一操作來改變你的當前位置：

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

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

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

• 如果你當前位于傳送門 $p_{v,1}$ ，你可以轉而使用傳送門 $p_{v,3}$，反之亦然。
• 如果你當前位于傳送門 $p_{v,2}$ ，你可以轉而使用傳送門 $p_{v,4}$，反之亦然。
  你不再能夠從傳送門 $p_{v,1}$
  轉至傳送門 $p_{v,2}$，或從傳送門 $p_{v,3}$ 轉至 $p_{v,4}$ ，反之亦然。

計算修改這一網絡使得每一個位置都可以從另外的每一個位置到達所需要花費的哞尼的最小數量。輸入保證存在至少一種修改網絡的合法方式。

輸入格式

輸入的第一行包含 $N$。

以下 $N$ 行每行描述一個結點。第 $v+1$ 行包含五個空格分隔的整數 $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$。

輸入保證對于每一個 $v$ ，$p_{v,1},p_{v,2},p_{v,3},p_{v,4}$ 各不相同，且每個傳送門出現在恰好兩個結點的鄰接表中。

輸出格式

輸出一行，包含修改這一網絡使得每一個位置都可以從另外的每一個位置到達所需要花費的哞尼的最小數量。

輸入輸出樣例 #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

說明/提示

樣例解釋

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

數據范圍與約定

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

思路

首先先翻譯一下這冗長的題目：

給定N個節點，對于每個節點u，u與4個傳送門相連，你可以從一個節點通過傳送門到達其他節點，且初始1，2號、3，4號傳送門是相連的。你可以花費$c_v$元改變連通順序，但原來的連通會被廢除

那么想要到達每一個節點嗎，我們只需要到達每一個傳送門即可，那樣例的圖可化為：

這時我們會發現，每一個連通塊恰好為一個環，那這有什么用呢？
由于我們需要將每個連通塊合并，但我們擔心的是如果我們調換傳送門的順序，我們會不會把當前的連通塊打碎？
由于每個連通塊恰好為一個環，我們改變順序后，肯定會打破兩條邊，而且這兩條邊一定不在一個環上，由此打破兩條邊后，會得到兩條鏈，將鏈連接起來后，又是一條環，這樣就可以一直合并。
不過我們還需要證明一下每一個連通塊必定是一個環
因為每個傳送門與兩個節點相連，所以他的度數為2(與其他傳送門相連的度數)，所以連通塊必定是一個環
那這樣就很好做了，我們一開始先將所有的連通塊處理出來，由于要連通，我們很容易就想到了最小生成樹，由此用kruskal求解即可

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int fa[N],n;
struct lit{int x,y,z;friend bool operator<(lit t1,lit t2){return t1.z<t2.z;}
}b[N];
int o=0;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){//合并int f1=find(x),f2=find(y);if(f1!=f2)fa[f1]=f2;
}
int main(){cin>>n;for(int i=1;i<=n*2;i++)fa[i]=i;//記得要初始化，而且是2*N個傳送門初始化for(int i=1;i<=n;i++){int c,x,y,z,w;cin>>c>>x>>y>>z>>w;merge(x,y);merge(z,w);//不需要花錢，直接合并b[++o]={x,z,c};//改變順序需要花費c元，由于z,w連通，改到x,z與x,w一致}sort(b+1,b+1+o);int ans=0;for(int i=1;i<=o;i++){int f1=find(b[i].x),f2=find(b[i].y);if(f1!=f2){fa[f1]=f2;ans+=b[i].z;}}//最小生成樹cout<<ans<<'\n';return 0;
}

總結

對于這種題目描述冗長的題目，一定要先簡化題目再做題，不要向我·一樣被題目所迷惑