题解

114 条题解

  • 0
    @ 2007-10-19 10:37:20

    第一次竟然交错程序了..

  • 0
    @ 2007-10-03 17:24:27

    PRIM就行,编起来简单

  • 0
    @ 2007-09-20 13:12:08

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    KRUSKAL 就是强

  • 0
    @ 2007-09-18 19:09:46

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    数据够弱

  • 0
    @ 2007-09-16 13:58:10

    用Prim一次ac 数据有点弱。。

  • 0
    @ 2007-07-29 14:42:21

    我不会做!!!

    555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555(最终泪流成河,有谁能帮帮我!!!)

  • 0
    @ 2007-07-24 19:30:35

    555 j打成i WA了N次 555

    最小生成树

  • 0
    @ 2007-07-23 13:42:38

    这题太难了,谁能干掉它,程序越简单越好

  • 0
    @ 2007-02-02 11:22:56

    我说...是RP问题还是咋地...

    一模一样的程序非得交两遍才过..

    还以为prim真不行呢``

  • 0
    @ 2006-12-18 22:34:35

    数据弱....

    用邻接矩阵+O(n^2)的Prim都能过....

  • 0
    @ 2006-12-02 22:50:58

    调了半天,不是快排写错,就是并查集写错……

    无言了,提交了N次……

    另外此题难度3??比NOIP2006的题都难??要是NOIP考这样的题我就HAPPY了啊~~

  • 0
    @ 2006-11-10 12:17:23

    不错 KRUSKAL+并查集+QSORT 一次AC

  • 0
    @ 2006-11-02 18:04:48

    方法:Kruskal

    缺点:又要写快排,又要写并查集,麻烦。(其他内容30行,kruskal用16行)

    心得:基础啊!!!!图论算法原版AC……

  • 0
    @ 2006-10-22 22:54:25

    繁忙的都市 各省青少年信息学奥林匹克竞赛 (Provincial OI) 竞赛原题

    编译通过...

    ├ 测试数据 01:答案正确... 9ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 9ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:18ms

    Prim吧..

  • 0
    @ 2006-10-18 21:32:02

    Qsort+Kruskal+并查集

  • 0
    @ 2006-10-08 21:14:36

    我比较倾向Kruskal,对Prim不是很熟。

    预处理用Qsort按权排序边,再来顺序加边。

    第一问输出n-1,第二问输出加的第n-1条边的权值。

    Qsort+Kruskal+并查集

    p.s此题是题库里难度3图论算法中最简单的一个了。

  • 0
    @ 2006-09-08 18:58:01

    分析题目后,不难建立出题目对应的模型:给出一个有边权的图,要求其中的一棵生成树,使得这棵生成树的最大边权最小。

    显然图的最小生成树是满足这个性质,下面用反证法证明最小生成树最大边权最小:

    反设图中存在一棵生成树T,T中的最大边权小于最小生成树Tmin的最大边权。令e是Tmin的最大边。e将Tmin分成两个连通分块X和Y。由于Tmin是最小生成树,那么对于任意边 ,都有e’的边权大于等于e的边权——结论1。而T是图的一棵生成树,那么T中一定存在一条边e’’ 属于 集合,而且e’’的边权一定小于e的边权。这与结论1矛盾,因此最小生成树最大边权最小的结论是成立的。

    因此只要用Prim或Kruscarl算法求出图的最小生成树即可。

  • 0
    @ 2006-09-19 21:50:19

    Prim....过了...!

    Prim跟边有什么关系吖...你每次枚举边就行了..判断起点和终点是否扩展到..

    落散牛说得太恐怖了..但是好像我的prim趋于kruskal..

  • 0
    @ 2006-08-29 16:29:26

    Kruskal。终于AC……感慨基础的重要~~~要不然也不会WA这么多次……

    Qsort+Kruskal

  • 0
    @ 2006-08-16 15:38:02

    绝对的MST,不过上面的两位牛为啥不支持Prim呢,难道Prim不能AC?

信息

ID
1190
难度
5
分类
树结构 | 生成树 点击显示
标签
递交数
2962
已通过
1132
通过率
38%
被复制
7
上传者