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