牛的旅行 题目描述 农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John就有多个牧场了。 John想在牧场里添加一条路径(注意，恰好一条)。对这条路径有以下限制： 一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：  (15,15) (20,15) D E *-------* | _/| | _/ | | _/ | |/ | *------...

产生数 题目描述 给出一个整数n(n<10^30)和k个变换规则(k≤15)。 规则： 一位数可变换成另一个一位数： 规则的右部不能为零。 例如：n=234。有规则（k=2）： 2－>5 3－>6 上面的整数234经过变换后可能产生出的整数为（包括原数）: 234 534 264 564 共4种不同的产生数 问题： 给出一个整数 n 和k 个规则。 求出： 经过任意次的变换（0次或多次），能产生出多少个不同整数。 仅要求输出个数。 输入格式 键盘输入，格式为： nk x1y1 x2y2 … … xnyn 输出格式 屏幕输出，格式为： 111个整数（满足条件的个数）： 输入输出...

血色先锋队 题目描述 巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。 军团是一个N行M列的矩阵，每个单元是一个血色先锋...

马的遍历   题目描述 有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步 输入格式 一行四个数据，棋盘的大小和马的坐标 输出格式 一个n乘m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1） 输入输出样例 输入 3 3 1 1 输出 0 3 2 3 -1 1 2 1 4 分析 这道题我们可以用广搜（BFS） 很简单，不会BFS的可以参考 骑士旅行（BFS） AC代码  #include<iostream> #include<cstdio> int n,m,x1,y1,hea...

离开中山路 题目描述 爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？ 输入格式 第1行：一个数 n 第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格） 第n+2行：四个数 x1,y1,x2,y2 输出格式 只有1行：最短到达目的地距离 输入输出样例 输入 3 001 101 100 1 1 3 3...

高手去散步 题目背景 高手最近谈恋爱了。不过是单相思。“即使是单相思，也是完整的爱情”，高手从未放弃对它的追求。今天，这个阳光明媚的早晨，太阳从西边缓缓升起。于是它找到高手，希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会，他已经准备好了一切。 题目描述 鳌头山上有n个观景点，观景点两两之间有游步道共m条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。 输入格式 第一...

最小花费 Description 在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。 Input 第一行输入两个用空格隔开的正整数n和m，分别表示总人数和可以互相转账的人的对数。以下m行每行输入三个用空格隔开的正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费(z<100)。最后一行输入两个用空格隔开的正整数A和B。数据保证A与B之间可以直接或间接地转账。 Output 输出A使得B到账100元最少需要的总费用。精确到小数点后8...

香甜的黄油 题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那） 输入格式 第一行: 三个数：奶牛数N，牧场数（2&...

单源最短路径 题目背景 本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。 题目描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入格式 第一行包含三个整数 n,m,s分别表示点的个数、有向边的个数、出发点的编号。 接下来 m 行每行包含三个整数 u,v,w表示一条 u→v的，长度为 w 的边。 输出格式 输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。 输入输出样例 输入 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出 0 2 4...

电车 题目描述 在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。 为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口A到路口B最少需要下车切换几次开关。 输入格式 第一行有3个整数2<=N<=100，1<=A，B<=N，分别表示路口的数量...

城市问题 Description   设有n个城市，依次编号为0，1，2，……，n-1（n<=100），另外有一个文件保存n个城市之间的距离(每座城市之间的距离都小于等于1000)。当两城市之间的距离等于-1时，表示这两个城市没有直接连接。求指定城市k到每一个城市i（0<=I,k<=n-1）的最短距离。 Input 第一行有两个整数n和k，中间用空格隔开；以下是一个NxN的矩阵，表示城市间的距离，数据间用空格隔开。 Output 输出指定城市k到各城市间的距离（从第0座城市开始，中间用空格分开） Sample Input 3 1 0 3 1 3 0 2 1 2 0 Sampl...

医院设置 题目描述 设有一棵二叉树，如图：  其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。如上图中， 若医院建在1 处，则距离和=4+12+220+240=136；若医院建在3 处，则距离和=4*2+13+20+40=81…… 输入格式 第一行一个整数n，表示树的结点数。(n≤100) 接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格(一个或多个)分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。 输出格式 一个整数，表示最...

工厂的烦恼 Description   某工厂发现厂里的机器在生产产品时要消耗大量的原材料，也就是说，有大量的原材料变成了废物。因此厂里想找出消耗原材料最大的一条生产线路进行改造，以降低成本。厂里的生产线路是一个有向无环网络，有N台机器分别代表网络中的N个结点。弧< I,j >(i < j)表示原材料从机器i传输到机器j的损耗数量。 Input 第一行是两个整数N，M（N<=100,M<=1000），分别表示网络的结点个数和弧数。第二行至M+1行，每行三个整数A，B，C，表示弧上的损耗为C。 Output 仅一个整数，为损耗最大的线路的损耗量。 Sample In...

最优贸易 NOIP 2009 提高组 第三题 题目大意 有n个点，有m个通道（有向或无向）。他要找到一条路，<stron>。在路上，买水晶球再卖掉水晶球，最后到n点。要求出他最大能赚多少钱（用卖水晶球的钱减买水晶球的钱） 分析 复杂的分析 下面深入理解 可以用两个spfa算法 邻接表建立，如图： 从1点去找，找到能到的点，并且赋值给他们：买水晶球最小的钱</stron> void spfa1(int o) {  minn[o]=w[o];//初值 head=0;tail=1; b[1]=o;c[o]=1; do {  head=head%N+1;//循环队列，否则会炸 ...