1. 首頁 > 生活百科 > >

Pictionary 方法記錄( 二 )

生活百科


審題題意轉化：
有\(n\)座城市；有\(m\)個時刻，在第\(i\)個時刻，所有\(m-i+1\)的倍數之間連邊；有\(q\)個詢問，詢問第\(x_i\)座城市和第\(y_i\)座城市什么時候連通 。
連邊（合并）連通城市的過程，其實就是對多個點建立集合，并進行合并的過程，所以考慮使用并查集 。
在對兩個城市進行連邊（即合并兩個點）時，欽定第一個城市是第二個城市的父親節點，并記錄這兩個點合并時的時間戳 。
查詢現詢問兩個點\((x,y)\)的最早連通時間 。\((x,y)\)的最早連通時間就是\(x\)到\(lca(x,y)\)中的最大時間戳加上\(lca(x,y)\)到\(y\)中的最大時間戳 。
為什么是最大值？兩個城市要想連通，就必須要等到路徑上最后一條邊建好才行 。
為什么是\(lca\)？題目中城市\(x\)和城市\(y\)的連通抽象到圖上就是\(x\)到\(y\)的一條樹上路徑（同一條邊不能重復走），也就是\(x\)->\(lca(x,y)\)->\(y\).這里不能包含\(lca(x,y)\)，因為這個點儲存的時間戳是和另一個點擊合并的時間 。
考慮\(lca\)的求法 。在處理并查集的時候，其實就處理出的圖上的每一個父子關系，我們可以將其利用起來：根據這些父子關系，\(x\)和\(y\)往上跳，從而找到\(lca(x,y)\).
但要想保存父子關系就不能使用路徑壓縮 ， 所以采用啟發式合并：將小集合合并到大集合，以起到優化的作用 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=100010;int n,m,q;int f[N],siz[N],dfn[N],dep[N];struct Edge//鏈式前向星存圖{ int u,v,nex;}e[N<<1];int head[N],tot;void add(int u,int v){ tot++; e[tot].u=u; e[tot].v=v; e[tot].nex=head[u]; head[u]=tot;}int maxx(int a,int b){ return a>b?a:b;}int find(int x)//并查集查找（不能用路徑壓縮）{ if(x==f[x]) return x; return find(f[x]);}void dfs(int u)//dfs求每個點相對于超級祖先的深度{ for(int i=head[u];i;i=e[i].nex) {int v=e[i].v;dep[v]=dep[u]+1;dfs(v); }}int main(){ scanf("%d%d%d",&n,&m,&q); int rt; for(int i=1;i<=n;i++) {f[i]=i;siz[i]=0; } for(int i=m;i>=1;i--) {for(int j=(i<<1);j<=n;j+=i)//對所有m-i+1的倍數之間連邊{int dx=find(i),dy=find(j);if(dx==dy){continue;}if(siz[dx]<siz[dy])//啟發式合并，將小集合合并到大集合{swap(dx,dy);}f[dy]=dx;add(dx,dy);rt=dx;//rt最終會記錄所有點的公共祖先，欽定這個“超級祖先”為根節點if(siz[dx]==siz[dy]){siz[dx]++;}dfn[dy]=m-i+1;//dfn記錄合并時的時間戳} } dfs(rt); for(int i=1;i<=q;i++) {int x,y;scanf("%d%d",&x,&y);int ans=0;if(dep[x]<dep[y]){swap(x,y);}while(dep[x]>dep[y]){ans=maxx(ans,dfn[x]);x=f[x];}while(x!=y){ans=maxx(maxx(dfn[x],dfn[y]),ans);x=f[x],y=f[y];}printf("%d\n",ans); }}參考

推薦閱讀