最优联通子集 洛谷题目传送门 这题在北大网站上也有POJ.1192 最优联通子集 Description 众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示，如果x, y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，则称P1, P2相邻，记作P1~P2，否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集，即S = {P1, P2,…, Pn}(n >= 1)，其中Pi(1 <=...

加分二叉树 题目传送门 题目描述 设一个 nn 个节点的二叉树 tree 的中序遍历为(1,2,3,…,n)，其中数字 1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 i 个节点的分数为 d i ​ ，tree 及它的每个子树都有一个加分，任一棵子树 \text{subtree}subtree（也包含 \text{tree}tree 本身）的加分计算方法如下： subtree 的左子树的加分 × subtree 的右子树的加分 + subtree 的根的分数。 若某个子树为空，规定其加分为 1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为...

二叉苹果树 题目传送门 Description 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点） 这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / 3 4 \ / 1  现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。 Input 第1行2个数，N和Q(1<=Q<= N,1 Output 一个数，最多能留住的苹果的数量。 Sample Input 5 2 1 3 1 1 4 ...

Anniversary party Description There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party fu...

选课 题目传送门 Description 大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。   每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。下面举例说明  上例中1是2的先修课，即如果要选修2，则...

战略游戏 题目传送门 Description   Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。   请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。 Input 输入文件中数据表示一棵树，描述如下：   第一行 N，表示树中结点的数目。   第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每...

将功补过 Case Time Limit:1000MS Description 作为间谍专家的Elvis Han受窃取X星球军事中心的秘密情报，他已经成功进入军事中心。但是很不幸的是，在他还没有找到任务需要情报的时候就被发现，这时他清楚他不可能完成任务了，不过还有机会将功补过，也就是得到一些不如任务情报有价值的其他情报，如果得到的情报的总价值大于等于任务情报价值，他也不会受到惩罚。很幸运的是他已经得到的军事中心的地图，情报都是隐藏在各个道路上的，但是他只有时间遍历一定数量的路（时间宝贵呀！还要逃跑。。）现在你做为他的助手，给你地图和每个道路情报价值，希望你分析出，看他能不能将功补过。   军事...

皇宫看守 Description 太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。 Input 帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 Output 输入文件中数据表示一棵树，描述如下： 第1行 n，表示树中结点的数目。 第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0对于一个n（0 < ...

Debug Description 经过了一整夜的激战，rc的部队终于攻下了虫族的首都Bugzilla。现在，rc决定亲自带领一队突击队员在虫族庞大的地道中寻找他的宿命之敌—Bug。   Bugzilla由N个基地组成。这N个基地被N-1段双向地道连接在一起，每段地道都连接两个基地，并且保证任意两个基地之间都可以通过地道互相到达。Bug就藏在其中的某段地道中。   开始时rc可以乘坐运输机降落在任何一个基地。每次到达一个基地时，rc都可以选择呼叫运输机将他和他的部队运输到任意另一个基地，或者进入与这个基地相邻的一段地道进行搜索。但为了防止Bug跑进已经搜索过的地道，他在离开一个基地进入地道或登...

软件安装 题目传送门 解题思路 1：这题可能形成环 所以要缩点，用强连通分量 void sd()//缩点 {  o=n; for(int i=1;i<=o;i++) for(int j=1;j<=o;j++) {  if(a[i][j]==1&&a[j][i]==1&&w[i]>0&&w[j]>0&&i!=j) {  o++; w[o]=w[i]+w[j]; v[o]=v[i]+v[j]; w[i]=w[j]=--o1; } if(a[d[j]][j]==1&&a[j][d[j]]==1&a...

鱼肉炸弹 Description 舒克和贝塔终于下定决心要去营救被关押在众猫聚居的A城中的大米同志。   A城的构造是很奇怪的。A城中的所有N栋建筑沿着一条直线排列，而且没有两栋楼的高度是相同的。而大米同志就被关押在其中的某栋建筑中。每一栋建筑的顶上都是有一些猫们在看守的。如果按照从一端到另一端的顺序将所有的建筑编号为1到N,那么第i栋建筑的高度为Hi，顶上的猫的数量为Ci.   每一只猫不但可以看守住其所在建筑的楼顶,还可以看守住一些比它所在建筑要低的楼的楼顶。前提是没有被其他楼所挡住。A城中的建筑都是很高的,高到可以忽略它们之间的距离和它们的水平面面积。于是可以认为，楼i上的猫能看守楼j的...

旅行计划 题目传送门 解题思路 这题就是拓扑排序+dp 先拓扑排序找相连的点 再用dp统计答案 拓扑排序 AC代码 #include<iostream> using namespace std; int n,m,x,y,h,t,num,tot,b[100005],c[100005],p[100005],head[200005],f[100005]; struct stu {  int to,next; }a[200005]; void add(int x,int y)//邻接表 {  tot++; a[tot].to=y; a[tot].next=head[x]; head[x]=...

奖金 Description 由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。   于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。 Input 两个整数n,m，表示员工总数和代表数； 以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。 Output 若无法找到合法方案，则输...

工程 Description 张三是某工程公司的项目工程师。一天公司接下一项大型工程，该公司在大型工程的施工前，先要把整个工程划分为若干个子工程，并把这些子工程编号为1、2、…、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工，公司需要工程师张三计算整个工程最少的完成时间。 对于上面问题，可以假设： 1、根据预算，每一个子工程都有一个完成时间。 2、子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。 3、只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也即同时施工的子工程个数不受限制。 例如：有五个子工程的工程规...