【Road】

【Road】

【问题描述】 给出一张n个点,m条边的无向图,摧毁每条边都需要一定的体力,并且花费的体力值 各不相同,给定图中两个点x,y(x≠y),每当(x,y)之间存在路径,就需要不断摧毁当前 图中花费体力最少的一条边,直到该路径不联通。他定义cost(x,y)为摧毁(x,y)之间路径 花费的体力和。 他想要求出这个结果: 【输入格式】 第一行两个整数n,m,表示点数...
【Tree】

【Tree】

【题目描述】 给你一堆边,其中有些边为黑色,有些边为白色,每条边有一条边权。 这些边一定能构造成一颗树,请问其中恰好选K条白边的最小生成树的权值和是多少? 【输入格式】 第一行三个整数n m k表示点数,边数,以及K 接下来m行每行四个整数u v w c表示u到c有一条权值为w颜色为c(0为白色1为黑色)的边(双向边) 【输出格式】 一行一个整数,表示恰好选...
【Highways】

【Highways】

题目描述 Wisekingdom 有 N 座城市,为了使 wisekingdom 的交通更加便利,国王决定修建高速公路,使得每两个城市之间都有高速公路相通。现在国王想知道的并不是修建的高速路的最小长度和。他感兴趣的是所建高速公路中最长的一条的长度,他希望这个最长长度尽量小。 输入格式 第一行:一个正整数 N ,  N<=500; 接下来 N 行,...
【Minimum】

【Minimum】

【问题描述】 给出一幅由n个点m条边构成的无向带权图。 其中有些点是黑点,另外点是白点。 现在每个白点都要与它距离最近的黑点通过一些边连接(就是最短路)(如果有很多歌,可以选取其中任意一个。),我们想要使得花费的代价最小。请问这个最小代价是多少? 【输入格式】 第一行两个整数n,m; 第二行n个整数,0表示白点,1表示黑点 接下来m行,每行三个整数x y z...
【最大异或和】

【最大异或和】

题目背景 USACO 2015 FEBRUARY CONTEST,SILVER——PROBLEM 3 SUPERBULL 题目描述 给定 N 个正整数 X1,X2 … XN 。 每次从 N 个正整数中选择两个数 Xi 和 Xj ,计算两数的异或值并累加入答案 S(S初始为0),然后删掉其中一个数(Xi或Xj),……,如此反复,直到只剩一个数...
【APIO2011 方块染色】

【APIO2011 方块染色】

题目描述 Description Sam和他的妹妹Sara 有一个包含n × m 个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好,他们想   要表格中每个2 × 2 的方形区域都包含奇数个(1 个或3 个)红色方格。例如,下图是一个合法的表格染色方案(在打印稿中,深色代表蓝色,浅色代表红色)。可是昨天晚上,有人已经给表格中的一些方格染上...
【NOI2015 程序自动分析】

【NOI2015 程序自动分析】

题目背景 NOI2015 DAY1 T1 题目描述 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本:假设 x1,x2,x3,…代表程序中出现的变量,给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件...
【NOIP2010提高组 关押罪犯】

【NOIP2010提高组 关押罪犯】

题目背景 NOIP2010提高组试题 题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为 1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱,他...
【CodeVS 1074 食物链】

【CodeVS 1074 食物链】

题目描述 Description 动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是“1 X Y”,表示X和Y是同类。 第二种说法是“2 X Y”,表...
【修建道路】

【修建道路】

题目描述 Farmer John最近得到了一些新的农场,他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达(也就是说,从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场)。有些农场之间原本就有道路相连。 所有 N(1<=N<=1,000) 个农场(用 1..N 顺次编号)在地图上都表示为坐标为(Xi,Yi)的点(0<=...
显示更多