题目描述已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图G = ( V , E ) ，其中V是顶点集合，E 是边集合，设D = [ d(i,j) ]是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。 输入输入数据由若干行组成;第一行为问题的规模N即城市的数目，剩下的N行为一个N*N的距离矩阵。 输出请输出周游路线的最短距离。 样例输入1234540 30 6 430 0 5 106 5 0 20 4 10 20 0 样例输出125 题解12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.util.Scanner; public class Main { ...

题目描述小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。 有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。 给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。 现在小杉要把一些云朵连在一起，做成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。 输入每组测试数据的 第一行有三个数N,M,K(1<=N<=1000,1<=M<=10000,1<=K<=10) 接下来M个数每行三个数X,Y,L，表示X云和Y云可以通过L的代价连在一起。(1<=X,Y<=N,0<=L<10000) 30%的数据N<=100,M<=1000 输出对每组数据输出一行，仅有一个整数，表示最小的代价。 如果怎么连都连不出K个棉花糖，请输出’No Answer’。 样例输入123 1 21 2 1 样例输出11 题解1234567891011121314151617181...

题目描述最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。 可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。 而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构： 在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。 输入输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值...

题目描述小哼和小哈一同坐飞机旅游，他们现在位于1号城市，目标是5号城市，可是1号城市并没有到5号城市的直航。不过小哼已经收集了很多航班信息，现在小哼希望找到一种乘坐方式使得转机的次数最少，如何解决呢？ 输入多组输入。 第一行输入n , m , start , end , 其中n表示城市数，m表示航线数，start表示起点城市，end 表示终点城市。紧接着输入m行，每行是一条类似a b这样的数据表示城市a和城市b之间有航线，也就是说城市a和城市b之间可以互相到达。 输出输出最少转机数,若不能到达请输出”Cannot reach”。 样例输入123456785 7 1 51 21 32 32 43 43 54 5 样例输出12 提示起终点为0时不可达 题解12345678910111213141516171819202122232425262728import java.util.Scanner;public class Main { private static final int INF = Integer.MAX_VALUE; public stati...

题目描述在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。 解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。 而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。 可以将弗洛伊德算法描述如下： 1.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是则更新它。 把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]&#...

题目描述河南省实验中学的一名教师T的一封辞职信引发热评，辞职的理由仅有10个字：“世界那么大，我想去看看”。网友评这是“史上最具情怀的辞职信，没有之一”。经采访得知，作者为2004年7月入职河南省实验中学的一名女心理教师，已经任职11年之久。如此任性的辞职信，领导最后还真批准了。 现在假设世界上有n个城市（用$1~n$标识 ），有m个高铁线路$e_i$格式为$x_i$ $y_i$ ;   T的开始城市$f$, 结束城市$e$，她希望把所有的道路都不重复的访问一遍，如果可以做到就输出$YES$否则输出$NO$ 输入城市数$n$和铁路$m$开始城市$f$和目的城市$e$每条铁路的起止城市$x_i$ $y_i$ 输出如果可以从开始城市$f$,结束城市$e$，并把所有路径都不重复的访问一遍，就输出$YES$否则输出$NO$ 样例输入12343 21 31 22 3 样例输出1YES 提示路线没有方向性，但是两个城市之间可能有多个线路 数据保证图一定是联通的 题解1234567891011121314151617181920#include <map>#include &l...

题目描述符文之地——瓦罗兰，作为最大的一块魔法大陆，它居于符文之地心脏中心，是符文之地面积最大的大陆。所有谋求符文之地霸权的势力，都将焦点放在了瓦罗兰。近200年来的战争和纷争导致魔法滥用，军队用法术和符文武装自己，英雄们打造出大部分魔法物品率领部队厮杀。他们拥有近乎无限的原始魔法力量使用，从未考虑过无止境的滥用魔法会给这片大陆的环境带来怎么样的灾难。最后两次符文之战影响了瓦罗兰的地质环境。地震和魔法风暴让整个瓦罗兰为之颤抖，对人们来说这份恐惧远超过战争的恐怖。人们终于意识到世界已经承受不起符文之战的破坏。为了回应世界上不断恶化的政治和经济危机，瓦罗兰的大法师们达成共识，冲突以可控和系统化的方式来处理。他们成立了一个叫英雄联盟的组织。但联盟的纷争并没有消失,以德玛西亚和诺克萨斯等阵营的英雄们继续为他们的信念而战。  输入第一行有两个整数$n,m$。n$(0<n<100)$表示有n个英雄；m$(0<m<100)$表示接下来有m行数据。接下来m行，每行都有两个整数a,b。表示a，b英雄在同一个阵营。在默认情况下，任意两个英雄不在同一阵营。 输出输出n个英雄的阵...

【问题描述】有一种加密方法为：其使用一个字母串（可以含重复字母，字母个数不超过50）作为密钥。假定密钥单词串为feather，则先去掉密钥单词中的重复字母得到单词串feathr，然后将其反序，并将字母表中的其它字母以反序追加到后面：  r  h  t  a  e  f  z  y  x  w  v  u  s  q  p  o  n  m  l  k  j  i  g  d  c  b  加密字母的对应关系如下：  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z  r  h  t  a  e  f  z  y  x  w  v  u  s  q  p  o  n  m  l  k  j  i  g  d  c  b 其中第一行为原始英文字母，第二行为对应加密字母。其它字符不进行加密。编写一个程序，用这种密码加密输入的字符串。假定输入的待加密字符串中的字母全为小写字母，并且输入密钥也全为小写字母。 【输入形式】从标准输入中输入密钥串，然后在下一行输入要加密的字符串。密钥串字母个...

题目描述小五同学最近在仓库工作，他在仓库里发现了一种斜条纹的木箱（请自行脑补），于是想用二位数组来模拟木箱的一面，然后把条纹填满数，再读出来。如下所示： 1 2 4 3 5 7 6 8 9 这一面读出来就是$1 2 3 4 5 6 7 8 9$，空格分开（最后一个数后面也有空格） 那他现在随手填了几个数字，让你帮忙按照上面的顺序读取一下。 输入多组输入 第一行输入3<=n<=20，代表一个n x n的矩阵。 然后下面n行就是每行的数字。 输出请你输出按照上面的顺序读取出来的数列。 样例输入12345678931 2 34 5 67 8 941 2 3 45 6 7 89 10 11 1213 14 15 16 样例输出121 2 4 3 5 7 6 8 9 1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16 题解12345678910111213141516171819202122232425262728293031323334353637#include <iostream>#include <c...

题目描述小哼通过秘密方法得到一张不完整的钓鱼岛航拍地图。钓鱼岛由一个主岛和一些附属岛屿组成，小哼决定去钓鱼岛探险。下面这个$10*10$的二维矩阵就是钓鱼岛的航拍地图。图中数字表示海拔，0表示海洋，$1~9$都表示陆地。小哼的飞机将会降落在$(6,8)$ ,即$g[5][7]=4$处，现在需要计算出小哼降落所在岛的面积（即有多少个格子）。注意此处我们把与小哼降落点上下左右相链接的陆地均视为同一岛屿。 输入多组输入$n,m,x,y$ $$n<=100$$ $$m<=100$$ $$0<x<=n$$ $$0<y<=m$$ 其后$n*m$个数字 输出输出面积 样例输入123456789101110 10 6 81 2 1 0 0 0 0 0 2 33 0 2 0 1 2 1 0 1 24 0 1 0 1 2 3 2 0 13 2 0 0 0 1 2 4 0 00 0 0 0 0 0 1 5 3 00 1 2 1 0 1 5 4 3 00 1 2 3 1 3 6 2 1 00 0 3 4 8 9 7 5...