Problem

【SHOI2010】最小生成树

Time Limit:
Memory Limit:

Description

最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个个点、条边的无向图的最小生成树有一个算法和另一个的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 中所示的都是图 中的无向图的最小生成树：

当然啦，这些都不是今天需要你解决的问题。想知道对于某一条无向图中的边，至少需要多少代价可以保证边在这个无向图的最小生成树中。为了使得边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 ，再把图中除了这条边以外的边，每一条的权值都减少。如图 所示就是一次这样的操作：

Input

输入文件的第一行有个正整数、、分别表示无向图中的点数、边数、必须要在最小生成树中出现的边的标号。
接下来行依次描述标号为的无向边，每行描述一条边。每个描述包含个整数、、，表示这条边连接着标号为、的点，且这条边的权值为。
输入文件保证,,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行，这行只有一个整数，即，使得标号为边一定出现最小生成树中的最少操作次数。

Problem

方格取数

Time Limit:
Memory Limit:

Description

在一个的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

Input

第一行一个数（），接下来行每行个数描述一个方阵

Output

仅一个数，即最大和

Problem

千钧一发

Description

Input

第一行一个正整数。
第二行共包括个正整数，第 个正整数表示。
第三行共包括个正整数，第 个正整数表示。

Output

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

Problem

Number

Description

有个正整数，需要从中选出一些数，使这些数的和最大。
若两个数同时满足以下条件，则不能同时被选

1. 存在正整数，使

Input

第一行一个正整数，表示数的个数。
第二行个正整数。

Output

最大的和。

Problem

【IOI2011】Race

Description

给一棵树,每条边有权.求一条简单路径,权值和等于,且边的数量最小.,

Input

第一行 两个整数
第二至行 每行三个整数，表示一条无向边的两端和权值 (注意点的编号从开始)

Output

一个整数 表示最小边数量，如果不存在这样的路径，输出

Problem

聪聪可可

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画个“点”，并用条“边”把这个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第行包含个正整数。后面行，每行个整数、、，表示号点和号点之间有一条边，上面的数是。

Output

以即约分数形式输出这个概率（即“”的形式，其中和必须互质。如果概率为，输出“”）。

Problem

【JOI2013】稻草人

Description

村有一片荒地，上面竖着个稻草人，村民们每年多次在稻草人们的周围举行祭典。
有一次，村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：

• 田地的形状是边平行于坐标轴的长方形
• 左下角和右上角各有一个稻草人
• 田地的内部（不包括边界）没有稻草人

给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数。

Input

第一行一个正整数，代表稻草人的个数。
接下来行，第行包含个由空格分隔的整数和，表示第个稻草人的坐标。

Output

输出一行一个正整数，代表遵从启示的田地的个数。

Problem

【AMPPZ2014】The Cave

Time Limit:
Memory Limit:

Description

给定一棵有个节点的树，相邻两点之间的距离为。
请找到一个点，使其满足所有条限制 ，其中第条限制为

Input

第一行包含一个正整数()，表示数据组数。
对于每组数据，第一行包含两个正整数()，表示点数、限制数。
接下来行，每行两个正整数()，表示树上的一条边。
接下来行，每行三个正整数(, )，描述一条限制。
输入数据保证所有之和不超过 ，所有之和也不超过 。

Output

输出行。第行输出第组数据的答案，如果无解输出，否则输出，
然后输出，如有多组解，输出任意一组。

Problem

【NOIp2007】Core树网的核

Time Limit:
Memory Limit:

Description

设 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称为树网（），其中分别表示结点与边的集合，表示各边长度的集合，并设有个结点。 路径：树网中任何两结点都存在唯一的一条简单路径，用表示以为端点的路径的长度，它是该路径上各边长度之和。我们称为两结点间的距离。 一点到一条路径的距离为该点与上的最近的结点的距离： 。 树网的直径：树网中最长的路径称为树网的直径。对于给定的树网，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距：树网中距路径最远的结点到路径的距离，即 。 任务：对于给定的树网和非负整数，求一个路径，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过（可以等于），使偏心距最小。我们称这个路径为树网的核（）。必要时，可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中，与是两条直径，长度均为。点是树网的中心，边的长度为。如果指定，则树网的核为路径（也可以取为路径），偏心距为。如果指定（或、），则树网的核为结点，偏心距为。

Input

包含行： 第行，两个正整数和，中间用一个空格隔开。其中为树网结点的个数，为树网的核的长度的上界。设结点编号依次为。 从第行到第行，每行给出个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“”表示连接结点与的边的长度为。 所给的数据都是正确的，不必检验。

Output

只有一个非负整数，为指定意义下的最小偏心距。

Problem

【AMPPZ2014】The Prices

Description

你要购买种物品各一件，一共有家商店，你到第家商店的路费为，在第家商店购买第种物品的费用为，求最小总费用。

Input

第一行包含两个正整数(,)，表示商店数和物品数。
接下来行，每行第一个正整数()表示到第家商店的路费，接下来个正整数，
依次表示()。

Output

一个正整数，即最小总费用。