1~n盒子都會向指定的盒子專遞第任意個盒子的信息，當自己的信息被其他盒子傳遞給自己時，這個游戲就結束了，詢問一共可以傳遞幾輪。一開始就是想暴利他，結果代碼寫得很亂，有細節漏洞，并且雖然數據不大，但時間復雜度仍過不了。然后就只好去學習圖論中的并查集求最小環。用每個節點代表每個盒子，如果傳遞了就在兩個節點之間加一條邊，當出現一個環時則代表游戲結束，這時候把這兩個點的路徑+1就是他們的路徑，也就是進行的輪數了。

1.并查集的初始化要寫好，別忘記加

2.把路徑理解好，找祖先的時候時d[當前]=d[祖先]+d[當前],合并不連通時是d[a]=d[b]+1;

3.

4.

代碼

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int f[10000001];//存儲祖先節點 int d[10000001];//存儲祖先節點的路徑長; int n,last; int minn=0x7fffff; void init(){ for(int i=1;i<=n;i++){f[i]=i;}return; } int get_f(int x){if(f[x]!=x){int last=f[x];//記錄父親節點f[x]=get_f(f[x]);//遞歸找到父親節點d[x]+=d[last];//將從自己到老父節點與父節點到新父節點的邊相加 }return f[x];//return x; } void merge(int a,int b){int t1=get_f(a);int t2=get_f(b);if(t1!=t2){//要是不相連 f[t1]=t2;//連上 d[a]=d[b]+1;//更新路徑 /*f[t2]=t1;d[a]=a[b]+1;//不一樣嗎 ？？*/ }else minn=min(minn,d[a]+d[b]+1);//假如已經連接,出現了環 ？？ return; } int t; int main(){cin>>n;init();for(int i=1;i<=n;i++){cin>>t;merge(i,t);//檢查兩節點是否相通 }cout<<minn;return 0; }

?

轉載于:https://www.cnblogs.com/china-mjr/p/11355274.html

總結

以上是生活随笔為你收集整理的P2611信息传递的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。