銀河英雄傳說(shuō)

luogu 1196

ssl 1225

題目大意：

有n列船，每列一開(kāi)始有一艘船，可以將某一艘船所在的列所有船接到另外一列，然后會(huì)問(wèn)某兩艘船是否在一列，如果在那中間有多少艘船

原題：

題目描述

公元五八○一年，地球居民遷至金牛座α第二行星，在那里發(fā)表銀河聯(lián)邦創(chuàng)立宣言，同年改元為宇宙歷元年，并開(kāi)始向銀河系深處拓展。
宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬(wàn)余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬(wàn)艘戰(zhàn)艦迎敵。
楊威利擅長(zhǎng)排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場(chǎng)劃分成$30000$列，每列依次編號(hào)為$1,2,\dots ,30000$。之后，他把自己的戰(zhàn)艦也依次編號(hào)為$1,2,\dots ,30000$，讓第$i$號(hào)戰(zhàn)艦處于第$i$列$(i=1,2,\dots ,30000)$，形成“一字長(zhǎng)蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會(huì)多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實(shí)施密集攻擊。合并指令為$M_{i,j}$ ，含義為第$i$號(hào)戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。顯然戰(zhàn)艦隊(duì)列是由處于同一列的一個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會(huì)使隊(duì)列增大。
然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過(guò)龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽(tīng)楊威利的艦隊(duì)調(diào)動(dòng)指令。
在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢(xún)問(wèn)指令：$C_{i,j}$ 。該指令意思是，詢(xún)問(wèn)電腦，楊威利的第$i$號(hào)戰(zhàn)艦與第$j$號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。
作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫(xiě)程序分析楊威利的指令，以及回答萊因哈特的詢(xún)問(wèn)。
最終的決戰(zhàn)已經(jīng)展開(kāi)，銀河的歷史又翻過(guò)了一頁(yè)……

輸入輸出格式

輸入格式：

第一行有一個(gè)整數(shù)$T(1\le T\le 500,000)$，表示總共有TT條指令。
以下有TT行，每行有一條指令。指令有兩種格式：$M_{i,j}$：$i$和$j$是兩個(gè)整數(shù)$(1\le i,j\le 30000)$，表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特竊聽(tīng)到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第$i$號(hào)戰(zhàn)艦與第$j$號(hào)戰(zhàn)艦不在同一列。$C_{i,j}$ ：$i$和$j$是兩個(gè)整數(shù)$(1\le i,j\le 30000)$，表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特發(fā)布的詢(xún)問(wèn)指令。

輸出格式：

依次對(duì)輸入的每一條指令進(jìn)行分析和處理：
如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦隊(duì)排列發(fā)生了變化，你的程序要注意到這一點(diǎn)，但是不要輸出任何信息；
如果是萊因哈特發(fā)布的詢(xún)問(wèn)指令，你的程序要輸出一行，僅包含一個(gè)整數(shù)，表示在同一列上，第$i$號(hào)戰(zhàn)艦與第$j$號(hào)戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第$i$號(hào)戰(zhàn)艦與第$j$號(hào)戰(zhàn)艦當(dāng)前不在同一列上，則輸出$?1$。

輸入輸出樣例

輸入樣例：

4 M 2 3 C 1 2 M 2 4 C 4 2

輸出樣例：

-1 1

說(shuō)明

【樣例說(shuō)明】

戰(zhàn)艦位置圖：表格中阿拉伯?dāng)?shù)字表示戰(zhàn)艦編號(hào)

解題思路：

每一艘船為一個(gè)點(diǎn)，當(dāng)要合并時(shí)，連接兩個(gè)點(diǎn)，更節(jié)點(diǎn)為最前面的，然后還要用一個(gè)$front$數(shù)組來(lái)存前面有多少艘船，然后求距離直接用$front$來(lái)相減求出

代碼：

#include<cstdio> #define abs(a) ((a)<0?-(a):(a))//手打abs using namespace std; int n,x,y,xx,yy,dad[30005],front[30005],num[30005]; char c; int find(int dep)//并查集 {if (dad[dep]==dep) return dep;int s=find(dad[dep]);front[dep]+=front[dad[dep]];//累加，前面有多少個(gè)點(diǎn)就加上，不用擔(dān)心會(huì)重復(fù)加，他加過(guò)一次就會(huì)練到根節(jié)點(diǎn)，然后就不會(huì)再加了return dad[dep]=s; } int main() {scanf("%d",&n);for (int i=1;i<=30000;++i)dad[i]=i,num[i]=1;for (int i=1;i<=n;++i){c=getchar();while (c!='M'&&c!='C') c=getchar();scanf("%d %d",&x,&y);xx=find(x);yy=find(y);if (c=='M'){dad[xx]=yy;//連接front[xx]+=num[yy];//num表示當(dāng)前列有多少個(gè)點(diǎn)，前面多了一排num[yy]+=num[xx];//后面多了一排}else xx==yy?printf("%d\n",abs(front[x]-front[y])-1):printf("-1\n");//在同一列就輸出，否則-1} }

總結(jié)

以上是生活随笔為你收集整理的【并查集】银河英雄传说 （luogu 1196/ssl 1225）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。