书的复制 Description 现在要把m本有顺序的书分给k个人复制（抄写），每个人的抄写速度都一样，一本书不允许分给两个或两个以上的人抄写，分给每个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写最多的人用去的时间。 Input 第一行两个整数，m,k(k<=m<=500) 第二行为m个整数，第i个数表示第i本书的页数。 Output 最短时间 Sample Input 9 3 1 2 3 4 5 6 7 8 9 Sample Output 17 分析 这题我们可以用动态规划（DP）做 要注意初值，然后...

没有上司的舞会 题目描述 某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 输入格式 第一行一个整数N。(1<=N<=6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最...

电子眼 Description 中山市石一个环境优美、气候宜人的小城市。因为城市的交通并不繁忙，市内的道路网很稀疏。准确地说，中山市有N-1条马路和N个路口，每条马路连接两个路口，每两个路口之间最多只有一条马路。作为一条交通网络，显然每两个路口之间都是可达的。为了更好地管理中山市的交通，市长决定在一些路口加装电子眼，用来随时监视路面情况。这些装在路口的电子眼能够监视所有连接到这个路口的马路。现在市长想知道最少需要在多少个路口安装电子眼才能监视所有的马路。市长已经把所有的路口都编上了1～N的号码。 给你中山市的地图，你能帮忙吗？ Input 输入文件traffic.in的第1行包括一个数字N(1...

文章目录  ***求连通分量*** **1.深搜（邻接矩阵）** **2.深搜（邻接表）** **3.广搜（邻接矩阵）** **4.广搜（邻接表）** **5.STL（邻接表）**   ***谢谢欣赏***    求连通分量 Description 求一个图的连通分量  Input n 顶点数小于等于100 Output 连通分量 Sample Input 8 6 3 1 2 2 5 5 4 4 1 8 7 0 0   文章目录  ***求连通分量*** **1.深搜（邻接矩阵）** **2.深搜（邻接表）** **3.广搜（邻接矩阵）** **4.广搜（邻接表）** **5.STL（邻接表）...

守望者的逃离 题目描述 恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最...

奇怪的电梯 题目描述 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤N)上有一个数字Ki(0≤Ki ≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,5代表了Ki(K1=3,K2=3,…)，从1楼开始始。在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有−2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入格式 共二行。 第一行为33个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N) 第二行为NN个用空格隔开的非负...

连通图 Description 判断一个图是否为一个边通图 Input n 顶点 (n<=100) 边 Output 1 表示连通 0 表示不边通 Sample Input 5 1 2 2 3 5 4 0 0 Sample Output 0 分析 这题是无向图，可以用到前面的求连通分量（DFS）（BFS）（STL）中的任意一种方法 稍加修改就行了 我用的是5.STL（邻接表） AC代码 #include<iostream> #include<queue> using namespace std; int b[105],head[10005],x,y,n,sum,t...

货员的难题 这题我在洛谷得了80分，此结果仅供参考 题目描述 某乡有n个村庄(1<n≤40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 输入格式 村庄数n和各村之间的路程(均是整数)。 输出格式 最短的路程。 输入输出样例 输入 3 0 2 1 1 0 2 2 1 0 输出 3 分析 这题我们可以用深搜（DFS）（邻接表）来做 依题意我们...

游乐场 Description 据新闻报道，Orz教主在太平洋中央建了一个大游乐园，其中有许多小岛，每个小岛上有且仅有一个游乐设施，有的小岛与小岛之间有海底隧道连接，而有的没有，一个游乐设施对一个人只开放一次，花的钱与得到的快乐值成正比。一开始，你可以选择被空投到任意一个小岛。当你想离开游乐园时，你可以打电话叫飞机来接，但不能再次被空投。 fhn非常有钱，他想在游乐园里得到最大的快乐值。 而czm则比较穷，他的愿望只是玩最多的游乐设施。 Input 第一行： n (代表有n个小岛)（n<=200） 以下n行，依次表示使用小岛1–小岛n上的游乐设施所花的钱 e (代表有e条海底隧道) 接着...

骑马修栅栏 Description 农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。 每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。 你的程序必须输出骑马的路径(用路上依次...

最优布线问题 Description 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。 现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。 Input 输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n...

最短网络 Description   农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000 Input 第一行： 农场的个数，N（3<=N<=100）。 第二行…结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实...

剑鱼行动 Description 给出N个点的坐标，对它们建立一个最小生成树，代价就是连接它们的路径的长度，现要求总长度最小。N的值在100以内，坐标值在[-10000,10000].结果保留二位小数 Input 5 ---------------5个点 0 0 ---------------5个点点的坐标 0 1 1 1 1 0 0.5 0.5 Output 2.83 分析 这题我们可以套模板——最小生成树 最优布线问题（最小生成树） 还有，这里有个知识点 坐标与坐标之间的距离（勾股定理） 求距离 代码实现 sqrt((abs(x[i]-x[j]))*(abs(x[i]-x[j]))+(ab...

控制公司 题目描述 有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。(此处略去一句废话）据说，如果至少满足了以下三个条件之一，公司A就可以控制公司B了： 公司A = 公司B。 公司A拥有大于50%的公司B的股票。 公司A控制K(K >= 1)个公司，记为C1, …, CK，每个公司Ci拥有xi%的公司B的股票，并且x1+ … + xK > 50%。 给你一个表，每行包括三个数(i,j,p)；表明公司i享有公司j的p%的股票。计算所有的数对(h,s)，表明公司h控制公司s。至多有100个公司。 写一个程序读入N组数(i,j,p)，i,j和p是都在范围(1…1...