《原神攻略》璃月特產琉璃百合採集路線分享

Z时代
2024-01-10
分类：游戏

程式碼實現：
通過路徑壓縮把某類節點統統併入根節點，類似於冠狀病毒(?

首先把每個節點的父節點設定為他們自己

find函式以及修改父節點程式碼實現

int findset(int n){
return fa[n]==n?n:fa[n]=findset(fa[n]);
}

並查集父節點查詢與融合操作

int fx=findset(x),fy=findset(y);
if(fx==fy) continue;//父節點相同說明在同一區間內
            fa[fx]=fy;

啟發式合併：額外增加一個siz陣列記錄在父節點為i的情況下，子節點的個數，當兩個區域融合時，讓子節點個數少的區域優先被修改

int fx=findset(x),fy=findset(y);
if(fx==fy) continue;
if(siz[x]>siz[y])\\保證fx<fy
                swap(fx,fy);
            fa[fx]=fy;
            siz[fy]+=siz[fx];

例題:行進路線 - 題目 - Daimayuan Online Judge

#pragma GCC optimize(2)
#pragma GCC optimize(1)
#include<bits/stdc++.h>
typedef longlong ll;
typedef unsigned longlong ull;
const ull base=131;
#define MAX 1009
#define PI 3.141592653589793
usingnamespace std;
ll node[MAX][3],fa[MAX];
int findset(int n){
return fa[n]==n?n:fa[n]=findset(fa[n]);
}
inline void solve(){
    ll xe,ye;cin>>xe>>ye;
int time;cin>>time;
for(int i=1;i<=time;i++){
        cin>>node[i][0]>>node[i][1]>>node[i][2];
    }
for(int i=0;i<time;i++) fa[i]=i;
    node[0][0]=0;node[0][1]=0;node[0][2]=1;
for(int i=0;i<=time;i++)
for(int j=i+1;j<=time;j++){
if((node[i][0]-node[j][0])*(node[i][0]-node[j][0])+(node[i][1]-node[j][1])*(node[i][1]-node[j][1])<=(node[i][2]+node[j][2])*(node[i][2]+node[j][2])){
int fx=findset(i),fy=findset(j);
if(fx==fy) continue;
                fa[fy]=fx;
            }
        }
int dex=-1;
for(int i=0;i<=time;i++){
if((node[i][0]-xe)*(node[i][0]-xe)+(node[i][1]-ye)*(node[i][1]-ye)<=node[i][2]*node[i][2])
                dex=i;
       }
if(dex!=-1&&findset(0)==findset(dex))
        cout<<1<<endl;
else
    cout<<0<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
int sum;cin>>sum;
while(sum--){
        solve();
    }
}