NOIP基础图论.doc

cowtract（网络）题目描述：  Bessie受雇来到John的农场帮他们建立internet网络农场有 N (2<= N <= 1,000)牛棚，编号为1..NJohn之前已经勘测过，发现有 M (1<= M <= 20,000)条可能的连接线路，一条线路是连接某两个牛棚的每条可能的线路都有一个建设费用 C (1<= C <=100,000)John当然想花尽量少的钱，甚至克扣Bessie的工钱  Bessie发现了这点，很生气，决定给John捣乱她要选择一些线路组成网，但费用却尽可能大当然网络要能正常工作，也就是任意两个牛棚之间都是相互可以连通的，并且网络上不能有环，不然John会很容易发现的  请计算组建这种网络最多可能的费用输入文件 cowtract.in第一行：两个整数 N M下面M行：每行3个整数 A，B，C表示一个可能的线路要连接A、B两个牛棚，费用是C输出文件 cowtract.out只一行，一个整数，即花费最大的费用如果不可能连接通所有牛棚，输出-1样例输入5 81 2 31 3 72 3 10       2 4 42 5 83 4 63 5 24 5 1717 + 8 + 10 + 7 = 42输出42 有点不同提交文件：b.exe输入文件：b.in输出文件：b.out题目描述： 最小生成树是图论中一个很常见的问题。

对你来说应该也是很简单的现在这道题和普通的最小生成树有点不同 给定一个带权无向图G(V, E)，如果T是G的一棵生成树，定义value(T) = max{ value(e) | e is in T } – min{ value(e) e is in T}，即value(T)是这棵生成树中最大权值的边与最小权值的边之差现在，我要你找出最小的value(T)输入格式(b.in):第一行是两个整数N和M，分别表示图G的顶点数和边数然后是M行，第i (1<=i<=M) 行含三个整数Xi (0

有一个信息要从最左边传送到最右边的单元格中每一次你可以从一个单元格向相邻的左或右单元格传送每一个单元格有一个价格P[i]，如果要传入单元格i，则要花费p[i]，另外，如果p[i]为-1，则表示不可以进入第i格  还有m部第i部的开始位置有enter[i]单元格，另一头在exit[i]单元格，你可以直接把信息从enter[i]传递到exit[i]，但你要花费的代价为：K + x，K是一个给定的定值，x则为之前你使用的次数如果你使用进入一个单元格j，则不须花费P[j]另外类似上面，价格为-1的单元格也是不可以进入使用的  现要你找一个花费C为最小的到达最右边单元格的方案花费C为最少的前提下，再求移动次数M最少的方案进入相邻格或使用都算一次移动数据范围0<=N,M<=50  0<=K<=10001<=P[i]<=1000  0<=p[0]<=10000<=enter[i],exit[i]<=N-1输入文件第一行一个整数Z(1<=Z<=20),表示有多少组测试数据每一组第一行：第一个数为N，后面有N个整数，对应P[i];      第二行：第一个数为M，后面有M个整数，相应表示enter[i];      第三行：第一个数为M，后面有M个整数，相应表示exit[i];      第四行：一个整数 K。

输出文件  对应每组测试数据，有一行两个整数：C  M  如果无解，输出两个"-1"样例输入21 100 1 0 1 0 10004 0 -1 0 0 1 0 1 2 100023 1 2 3 0 0 1003 1 0 -1 1 0 1 2 019 4  2  1  0  5  6  0  3  010 4  4  3  7  5  4  2  5  8  410 7  3  5  0  5  4  5  0  8  38输出0 0 1000 2 5 2 -1  -114  6 gentree给你一个无向连通图G，每点有个权值di （>0），要求生成一棵树根为1号节点的有根树T对于树中边e，e的代价为所有从根出发的且包含e的路径的终点权值的和现求生成树T，使得边的代价总和最小输入：第一行n,m分别为点数，边数N <= 1000; m <= 200000; 接下来m行，每行两个数 u,v描述边的两个端点最后一行 n个数，顺次给出每个点的权值输出：一个数，最小代价 样例输入：5 41 21 33 43 51 2 3 4 5样例输出：23。