九度OJ 题目1012:畅通工程

题目描述:     某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? 输入:     测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时,输入结束,该用例不被处理。 输出:     对每个测试用例,在1行里输出最少还需要建设的道路数目。 样例输入:

样例输出:

============================== 这个题目,概念上就是求非连通图里面联通子图的数量…道路嘛就是再加几条边能把各个联通子图连起来~ 做法的话,用并查集弄吧~ 并查集最简单的玩法就是,弄一个亲爹数组,数组里面存指向自己亲爹的指针,没爹的就是根了… 统计有几个没爹的就是统计有多少联通子图 ============================== #include using namespace std; int findRoot(int *parentAry, int currIndex) { if(parentAry[currIndex] == -1) return currIndex; //没爹了,currIndex就是爹 else { int rootIndex =
Continue reading 九度OJ 题目1012:畅通工程

九度OJ 题目1109:连通图

题目描述:     给定一个无向图和其中的所有边,判断这个图是否所有顶点都是连通的。 输入:     每组数据的第一行是两个整数 n 和 m(0<=n<=1000)。n 表示图的顶点数目,m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据,每行有两个值 x 和 y(0<x, y <=n),表示顶点 x 和 y 相连,顶点的编号从 1 开始计算。输入不保证这些边是否重复。 输出:     对于每组输入数据,如果所有顶点都是连通的,输出”YES”,否则输出”NO”。 样例输入:

样例输出:

==================================== 这两天弄几道简单的做做… 这个是图联通的检测,可以用DFS或者BFS做,其实函数给个int返回值,返回这个节点标记了几个,这样后面main函数里面就不用再遍历一次visited数组了~ 发现以前申请的空间都不delete的,现在感觉就像便便了没擦屁股一样… 调试出来第一遍发现怎么都不对,后来细看发现申请出来的二维数组没有初始化…噗 呐,如果是BFS的话,按照数据结构书上讲,用队列来搞,不用递归就行了。把本层访问到的节点塞到工作队列中就行.. ==================================== #include using namespace std; void DFS( bool **connMatrix, bool *visited, int N, int
Continue reading 九度OJ 题目1109:连通图

九度OJ 题目1172:哈夫曼树

题目描述: 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。 输出: 输出权值。 样例输入:

样例输出:

================================= 吐槽:VC6里面智能提示好像到while语句之类的循环里面就会失效,然后就只能盲打..Orz… ================================= #include #include #include using namespace std; struct Node { int val; Node *parent; Node() { parent = NULL; } int getHeight() { int h = 0; Node *p = parent; while(p != NULL) { h++; p = p->parent; } return h;
Continue reading 九度OJ 题目1172:哈夫曼树

九度OJ 题目1190:大整数排序

题目描述: 对N个长度最长可达到1000的数进行排序。 输入: 输入第一行为一个整数N,(1<=N<=100)。 接下来的N行每行有一个数,数的长度范围为1<=len<=1000。 每个数都是一个正数,并且保证不包含前缀零。 输出: 可能有多组测试数据,对于每组数据,将给出的N个数从小到大进行排序,输出排序后的结果,每个数占一行。 样例输入:

样例输出:

========================================== #include #include #include using namespace std; struct BigInt { char data[1001]; // 高位在前,低位在后 }; int compare(const void *pA, const void *pB) { BigInt *a = (BigInt *)pA; BigInt *b = (BigInt *)pB; int len_a = strlen(a->data); int len_b = strlen(b->data); if(len_a <
Continue reading 九度OJ 题目1190:大整数排序