1789专题
prime（最小生成树）——POJ 1789
对应POJ题目：点击打开链接 Truck History Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1789 Description Advanced Cargo Movement, Ltd.
POJ 1789 Prim 向愚蠢的堆优化告别
昨天+今天晚上，打限度为K的最小生成树可是打死我了。 却发现自己对 Prim 的理解有错。 自己之前写 Prim 的时候像写 dijskra 一样，在提取队列中最小的点的时候是用的优先队列。 以为这样可以优化复杂度，真是的。。。 后面反正要枚举一下所有的该点的邻接点的，这个操作是 O(n) 的，前面优化有个 P 用！ 最后 Prim 就是 O（n^2） 另外一种MST倒是可以用优先队列
POJ 1789最小生成树（kruscal算法）
这题其实是密的，比较适合用Prim算法，但是我现在想练习一下自己的并查集运用，所以只用了kruscal算法…… 题意就是字符串中，串与串比较，其中一串是拿来做参考，其他如果其中的字符改变最小，就是最佳的……就是代码继承…… 比如： 4aaaaaaabaaaaaaabaaaaaaabaaaa 第一行作为参考，第二行只用改一个b字母就和第一行一样了，第二行也是只用改一个字母，第三行也
POJ 1789最小生成树的水题，PRIM算法普通的实现版
题目大意 读入有N个7位的字符串，定义每个字符串之间的距离是他们之间不同字符的个数，然后就是求最小生成树的水题了 这题用不同方法做了几遍了，废话就不说开了， 只是我第一次写PRIM算法 增点集。。。就是PRIM算法中节点不断增加的点的集合 减点集。。。与增点集相反的点集,其中的点不断减少,直到为零算法就结束了 #include<iostream>#include<algorith
杭电OJ 1789：Doing Homework again
经典的贪心问题，先按照作业的扣除分数从大到小排序，如果分数相同则按截至日期从小到大排序。然后根据day判断哪些作业可以被安排。注意：for循环中如果存在一个作业符合条件就要跳出循环（因为每天只能安排一个作业）。 C++代码： #include<stdio.h>#include<algorithm>using namespace std;const int N=1001;struct
hihocoder 1789 阶乘问题（数论）
http://hihocoder.com/problemset/problem/1789 求一个最大的整数 m，使得 k^m 是 n! 的约数 我们可以看成是k^m*x=n！，且m为最大了，那意味着x不能拆成k*y了，所以我们就只要求n！中每个乘数拆成若干个质数相乘，然后求这些质数能组成多少个k。 因为是质数，所以都是互不干扰的，不存在重复的问题。 因此我们可以先求k是由哪些质数相乘
POJ 1789 解题报告
这道题是求最小生成树。很久之前是用kruskal算法求的（之前已经用过这个模板很多次），但是超时了，这里是稠密图，对所有边排序是非常耗时的操作。这里改用没有优化的prim算法（用的是数组而不是heap，这意味着每次选最近的节点都需要过一遍数组，O(N)）。但是还是很轻松地通过了。 thestoryofsnow1789Accepted160K438MSC++1591B /* ID: th
HDU 1789 Doing Homework again（经典贪心）
贪心题。 因为一门作业完成时间都是一天。 所以扣分多的自然要先完成。 先按照分值 从大到小排序，再按照 时间从大到小排序。 也就是 分值越高 越晚的先做。 #include <cstdio>#include <algorithm>#include <iostream>#include <cstring>#include <cmath>#include <cstdlib>#in
hdoj 1789 Doing Homework again 【贪心】
贪心策略：先按分数从大到小排序，分数一样，再按时间从小到大排序 分最高的越靠近期限完成，越好 话不多说直接看代码 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1789 代码： #include<cstdio>#include<cstring>#include<algorithm>using std::sort;typedef str
zoj - 1789 - The Suspects
题意：有n个学生，编号为0到n-1，m个群，给出每个群的学生，开始学生0被怀疑得了SARS，于是，人传人，被怀疑的学生所属群的所有学生都被怀疑，问共有几个学生被怀疑。 题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=789 ——>>简单的并查集题目，将每个群的后一个学生与前一个学生judge，统计结点数输出即可。
HRBUST 1789 通信道路（思维）
通信道路 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 36(25 users)Total Accepted: 20(19 users)Rating: Special Judge: No Description 某国正面临严峻的局势，为了确保国内秘密文件传输的安全，该国政府需要统计出国内城市间的通信情况。如果某文件