NOIP基础图论.doc

cowtract（网络）题目描述：Bessie受雇来到John的农场帮他们建立internet网络。农场有 N (2= N = 1,000)牛棚，编号为1.N。John之前已经勘测过，发现有 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 (0Xi=N), Yi (0Yi=N), Di(0Di=108), 表示图G中有一条边(Xi, Yi)，边权为Di。输入保证G是连通的，而且没有平行边（即两个点之间最多只有一条边）。输出格式(b.out):输出一个整数，表示最小的value(T)。输入样例：3 31 2 101 3 202 3 30输出样例：10数据说明：对于50%的数据，1=N=20，M = 200。对于100%的数据，1=N=100，M = 5000。CheapestRoute题目描述：有一列n个单元格组成的信息通道，从左至右标号为0至n-1。有一个信息要从最左边传送到最右边的单元格中。每一次你可以从一个单元格向相邻的左或右单元格传送。每一个单元格有一个价格Pi，如果要传入单元格i，则要花费pi，另外，如果pi为-1，则表示不可以进入第i格。 还有m部电话。第i部电话的开始位置有enteri单元格，另一头在exiti单元格，你可以直接把信息从enteri传递到exiti，但你要花费的代价为：K + x，K是一个给定的定值，x则为之前你使用电话的次数。如果你使用电话进入一个单元格j，则不须花费Pj。另外类似上面，价格为-1的单元格也是不可以进入使用电话的。 现要你找一个花费C为最小的到达最右边单元格的方案。花费C为最少的前提下，再求移动次数M最少的方案。进入相邻格或使用电话都算一次移动。数据范围0=N,M=50。 0=K=1000。-1=Pi=1000。 0=p0=1000。0=enteri,exiti=N-1输入文件第一行一个整数Z(1=Z0），要求生成一棵树根为1号节点的有根树T。对于树中边e，e的代价为所有从根出发的且包含e的路径的终点权值的和。现求生成树T，使得边的代价总和最小。输入：第一行n,m分别为点数，边数。N = 1000; m = 200000;接下来m行，