codevs 1003 電話連線

2019-11-06 06:04:38

字體：大中小

來源：轉載

供稿：網友

codevs 1003 電話連線

拿到這個題，看到說要用PRim算法，感覺是個模板題，不過好像自己也沒怎么寫過關于最小生成樹的題目，就嘗試著自己寫一個prim算法吧。基本思路是in[i]維護每個i是否在生成樹里面，用優先級隊列存儲邊struct,重載小于運算符，但是不知道為什么就是WA了。。現在也還沒相通。然后就去看題解了，不過確實是在下輸了，別人40幾行的代碼就可以搞定了，我70幾行的代碼還WA了。有時候漂亮的解法都可以把代碼寫得非常的簡潔漂亮，在下受教了。轉載以下一份題解代碼：#include<cstdio>int e[101][101],ans,book[101],fa[101],dis[101],que[101],count,n;//count記錄已經選擇了多少條邊//fa[que[i]]表示第i個加入生成樹的點的老爹，i和i的老爹也就是我們要輸出的邊int inf=99999999;int main(){ scanf("%d",&n); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) scanf("%d",&e[i][j]); for (int i=1; i<=n; i++) { dis[i]=e[1][i];//dis數組為記錄每個點到生成樹的最小距離 fa[i]=1; //fa表示每個點i的父親，也就是哪個點使得i得到松弛加入生成樹 } book[1]=1; //book數組標記每個點是否已經加入生成樹 for (int x=1; x<n; x++) { int min=inf,u; for (int i=1; i<=n; i++) if (book[i]==0 && dis[i]<min) { min=dis[i]; u=i; //que表示依次加入的點，也就是要按序輸出的點 que[count]=i; //新加入該生成樹的點 } ans += min; book[u] = 1; // u這個點加入了生成樹 if(min!=0 && min!=inf) count++;//當前選擇的新加入的點i是題目事先未連接的電話線，才把count++，表示新加入的邊 for (int i=1; i<=n; i++) if (book[i] == 0 && e[u][i] < dis[i]) //距離更小了 { dis[i]=e[u][i]; //更新這些點和最小生成樹的距離 fa[i]=u; //i得到松弛后更新i的老爹 } } printf("%d/n",count); for (int i=0; i<count; i++) if (fa[que[i]]<que[i]) printf("%d %d/n",fa[que[i]],que[i]); else printf("%d %d/n",que[i],fa[que[i]]); printf("%d",ans); return 0;}

4.今天已經連續被好多道題打擊了，腰有點酸，但還是要堅持下去，不畏挫折和艱難。

上一篇：中國（北方）大學生程序設計訓練賽（第一周）(Problem F: 等差區間-線段樹＋等差數列平方和公式)

下一篇：306. Additive Number