图-最小生成树

Prim 算法示例算法思想:代码import java.util.Scanner; public class main { static int Vnum=9; static int Map[][]=new int[Vnum][Vnum]; static int MAX=Integer.MAX_VALUE; public static void main(String[] args) { Scanner scanner=new Scanner(System.in); //初始化 for(int i=0;i<Vnum;i++) { for(int j=0;j<Vnum;j++) { if(i==j) { Map[i][j]=0; //(i,j)=0 } else { M...

P1583 魔法照片

题目描述一共有n(n≤20000)个人(以1--n编号)向佳佳要照片,而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序,每人就有了一个序号D[i](取值同样是1--n)。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1,显然类别序号的取值为1--10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后,最终的权值最大的k个人,并输出他们的编号。在排序中,如果两人的W[i]相同,编号小的优先。输入格式第一行输入用空格隔开的两个整数,分别是n和k。第二行给出了10个正整数,分别是E[1]到E[10]。第三行给出了n个正整数,第i个数表示编号为i的人的权值W[i]。输出格式只需输出一行用空格隔开的k个整数,分别表示最终的W[i]从高到低的人的编号。输入输出样例输入 #110 10 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20输出 #110 9 8 7 6 5 4...

1215:迷宫

题目描述一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。输入第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的 2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0 输出YES NO 代码:#include<iostream> using name...

扫雷游戏

时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld题目描述扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。输入描述:输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。接下来n行,每行m个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。输出描述:输出文件包含n行,每行m个字符,描述整个雷区。用’*’表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。示例1输入3 3 *?? ??? ?*? 输出*10 ...

1210:因子分解

题目1210:因子分解时间限制: 1000 ms 内存限制: 65536 KB提交数: 3307 通过数: 2025【题目描述】输入一个数,输出其素因子分解表达式。【输入】输入一个整数 n (2≤n<100)。【输出】输出该整数的因子分解表达式。表达式中各个素数从小到大排列。(幂次方不算 比如:3^2*5 也是正确)如果该整数可以分解出因子a的b次方,当b大于1时,写做 a^b ;当b等于1时,则直接写成a。【输入样例】60 【输出样例】2^2*3*5 【来源】No代码#include<iostream> using namespace std; int arr[101]; void dfs(int n,int i) { if (i > n || n == 1) /*边界 因子不包括1 因子不能大于本身*/ return; while (n%i == 0) /*能整除的才是因子*/ { arr[i]++; /*桶排序记录下来 方便输出幂次方...