当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] POJ2485 Highways(最小生成树)

    题意: 城市之间建高速公路,要求在能连通的情况下找出最小生成树最大的边 要点: 最小生成树,这题我学了一下prim算法。这个算法的要点是用点遍历,关键之处在于建立一个不断更新的low数组,这个数组记录生成树的过程中能接触到的对应最小权值。每次先随便选一个顶点作为起点,然后存入low数组,寻找一次当前...

    13
    热度
  • [综合] 无符号数的注意事项

    看CSAPP中着重强调了这个问题,很容易出错。两个无符号数之间比较不会出现问题,但如果两个无符号数相减,如果前一个数小于后一个数,不会输出有符号的负数,而是输出一个很大的无符号数(就是对应的有符号数转成无符号数),所以进行比较的时候要十分小心,一般两个无符号数比较大小直接用大于小于即可,如果相减后与...

    39
    热度
  • [综合] POJ1287 Networking(最小生成树)

    题意: 连通一个图,找最小权值和,有重边 要点: 因为有重边,所以Prim算法还要取最小的边加入,而Kruskal算法可以直接忽略这个问题,因为一开始要排序,大的自动舍掉了。这题很水,但我WA了快1个小时,原因init函数中,因为我是从0开始到n-1的,这题因为卡的比较紧,数据是从1~n的,所以这里...

    11
    热度
  • [综合] POJ1861 Network(最小生成树)

    题意: 有n个顶点,m条边,每条边双向的,并且有一定的长度,现在要求使每个顶点连通起来,并且使总长度最短输出最大边,和边的总数,还有是这些边的情况输出 要点: 这破题,specialjudge给的输出例子是错的,导致我先用prim算法搞了一个小时还是WA,怒换Kruskal算法10分钟AC了。不过用...

    97
    热度
  • [综合] POJ2395 Out of Hay(最小生成树)

    题意: 农场之间相互连接,要求输出最小连通中最长的那条边的权值 要点: 又是一道模板题,POJ上最小生成树咋这么多水题,要做点难的啊。 15347115 Seasonal 2395 Accepted 292K 79MS C++ 892B 2016-04-0313:07:56

    9
    热度
  • [综合] POJ2377 Bad Cowtractors(最大生成树)

    题意: 连接农场,要求输出最大权值和并且不能连成环,如果不能全部连接,输出-1 要点; 就是最小生成树变成最大罢了,Kruskal算法,排序改成从大到小,一次AC。 15347152 Seasonal 2377 Accepted 412K 63MS C++ 881B 2016-04-031...

    11
    热度
  • [综合] POJ2421 Constructing Roads(最小生成树)

    题意: 村庄之间连通,要求输出最小权值和,注意有些村庄已经连通 要点: Prim算法稍微变一下,因为是求权值和,已经连通的之间权值改为0即可,反正为0后面算的时候肯定是最小值,会加入集合的,然后权值又是0不影响。 15347342 Seasonal 2421 Accepted 208K 3...

    85
    热度
  • [综合] POJ2479POJ2593 Maximum sumMax Sequence(最大连续和)

    题意: 一组数列,分成两组,求怎么分使两组分别的连续最大和加起来最大,输出总和 要点: 最大连续和的一个简单变形,先从左往右求一次dp,将对应的当前最大值存储下来。然后从右往左dp一次,计算最大值即可。 POJ2479: 15350322 Seasonal 2479 Accepted 56...

    21
    热度
  • [综合] 贪心法经典问题总结

    乘船问题: 要点什么的看白书,解释的已经很详细了。从这道题我们可以证明贪心法不会丢失最优解,因此可以通过贪心得到最优解。 题目:点击打开链接 #include<stdio.h> #include<stdlib.h> #include<string.h> ...

    17
    热度
  • [综合] POJ2387 Til the Cows Come Home(最短路径)

    题意: 输入一个图,给出每条边的权值,以1为起点,要求到n的最短路径。 要点: 今天学了一下最短路,有好多种算法,估计要做好长一段时间了。这题就是最简单的模板,就是稍微注意一下可能有重边。这题用的dijkstra算法,主要是贪心,证明还不会。以后看看能不能推一下。 参考博客:点击打开链接点击打开链接...

    77
    热度
  • [综合] POJ1125 Stockbroker Grapevine(最短路径)

    题意: 这题真难读懂,简单来说就是n个经理人,每个经理人认识其他的一些经理人,要交流情报,每个经理人只能与认识的人交流,并且交流需要时间,要求从那个经理人开始传情报能使最慢收到情报的经理人耗时最短,输出最短时间 要点: 就是一个Floyd的模板问题,就是题目难懂了一点。 15368826 ...

    0
    热度
  • [综合] POJ1502 MPI Maelstrom(最短路径)

    题意: 邻接矩阵表示一个无向图,因此只给一半,x代表无法从i到j。 要点: 最短路径水题,用dijkstra直接过了,现在主要是练习一下bellman-ford算法和spfa算法。 dijkstra算法: 15369258 Seasonal 1502 Accepted 208K 0MS C+...

    63
    热度
  • [综合] POJ3259 Wormholes(最短路径)

    题意; 有n个农场,m条双向路,之中有w个虫洞,虫洞为单向路,从起点到终点耗时反而是负数,求能否追上自己也就是判断是否有负权回路。 要点: 负权回路就是回路的权值之和为负数的意思,只要出现负权回路了,无论什么算法都是求不出最短路径的。这里学习了一下bellman-ford算法,dijkstra算法虽...

    15
    热度
  • [综合] 第一次校赛总结

    搞了ACM快大半年了,虽然有点小成就,但还是弱的很。学校组织了一次校赛,我自不量力的去参加了一下,结果确实惨,就A了一道水题。说实在的,看了一下结题报告确实不是像我这种水平的能做的,都是没见过的算法,不会做也着实正常,毕竟我才大一,这比赛主要还是针对大二大三的。其实最后做下来,12道题里我有三道题是...

    69
    热度
  • [综合] POJ1860 Currency Exchange(最短路径)

    题意:: 有n种货币,m种兑换方式,每次兑换是这样计算的:如果一开始有V单位b货币,Rab是从a换到b的汇率,Cab是交换需要的手续费,最后能换到(V-Cab)*Rab单位b货币。一开始的货币种类是s,要求最后换回s,问能否进行一系列兑换,使最后换回s时钱增加。 要点: 如果能够经过一个回路返回起点...

    93
    热度
  • [综合] POJ2240 Arbitrage(最短路径:SPFA||Floyd)

    题意: 还是套汇问题,换货币看能不能增加钱 要点: 还是求负权回路,这题没有规定从哪边出发,所以Floyd算法比较好,但我刚学了一下spfa算法,强行用了一下也可以。 SPFA算法详解:点击打开链接 SPFA算法: 15380850 Seasonal 2240 Accepted 280K ...

    95
    热度
  • [综合] POJ3268 Silver Cow Party(最短路径)

    题意: 每个农场有一头牛,现在要到农场x开派对,路径是单向的,要求开完派对后还要回到原农场,求所有牛的最短路径的最大值 要点: 就是一个定终点求最短路径的变形,现在已经知道终点,从终点回到原农场的最短路径很好求,直接dijkstra算法即可,想求原农场到终点的最短路径只要将所有的单向路反向即可。利用...

    44
    热度
  • [综合] POJ2502 Subway(最短路径)

    题意: 从家到学校,给出家和学校的坐标,可以做地铁或走路,走路10KM/H,坐地铁40KM/H,地铁有很多条线路,每条线路之间有很多站点,给出每个站点的坐标(都是整数),要求到学校需要最短的分钟数(四舍五入后取整) 要点: 这题的输入简直日了狗了,线路的数目是以EOF结尾的,完全没办法验证数据。简单...

    67
    热度
  • [综合] POJ3250 Bad Hair Day(单调栈)

    题意: 给出一列牛的高度,所有牛只能往右看,且只能看到高度比自己低的牛的发型,并且如果出现高度大于自己的牛,后面的牛就再也看不到了,求所有牛能看到其他牛的发型总和。 要点: 刚刚教了单调栈和单调队列,虽然原理了解了,但是还是无法很好的转化,这就需要练习了。这题主要是看到牛的总数与被看到的牛的数量是相...

    91
    热度
  • [综合] POJ2796 Feel Good(单调栈)

    题意: 给出一列数据,要求一个区间内最小值与区间内数据总和乘积最大值 要点: 还是单调栈,这次我自己写的,先做了几题比较简单的果然还是有效果的,这题也是一样,按点遍历,网上大神做的是直接遍历一次即可,我看不太懂,还是自己写了一个往两侧寻找边界的,比较好理解,注意这题可以开一个sum数组存储第i个数据...

    16
    热度