- 浏览: 35562 次
- 性别:
- 来自: 湖南
最新评论
-
kulinglei:
提烟而过 写道问下楼主:你是拿了别人的注册号在这里害别人,还是 ...
折半搜索 -
jy00105276:
没看代码,看描述难道是2分法?
是的话不一定是a[i-1] ...
折半搜索 -
提烟而过:
问下楼主:你是拿了别人的注册号在这里害别人,还是没事在这里装- ...
折半搜索 -
zqynux:
fffvvvzz 写道11-15
是
11 12 13 14 ...
折半搜索 -
zqynux:
额,, 就是一个NOIP题目的答案..
vijos 谁拿了最多奖学金
Cow Tours
Farmer John has a number of pastures on his farm. Cow paths connect some pastures with certain other pastures, forming a field. But, at the present time, you can find at least two pastures that cannot be connected by any sequence of cow paths, thus partitioning Farmer John's farm into multiple fields.
Farmer John would like add a single a cow path between one pair of pastures using the constraints below.
A field's `diameter' is defined to be the largest distance of all the shortest walks between any pair of pastures in the field. Consider the field below with five pastures, located at the points shown, and cow paths marked by lines:
15,15 20,15
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
10,10 15,10 20,10
The `diameter' of this field is approximately 12.07106, since the longest of the set of shortest paths between pairs of pastures is the path from A to E (which includes the point set {A,B,E}). No other pair of pastures in this field is farther apart when connected by an optimal sequence of cow paths.
Suppose another field on the same plane is connected by cow paths as follows:
*F 30,15
/
_/
_/
/
*------
G H
25,10 30,10
In the scenario of just two fields on his farm, Farmer John would add a cow path between a point in each of these two fields (namely point sets {A,B,C,D,E} and {F,G,H}) so that the joined set of pastures {A,B,C,D,E,F,G,H} has the smallest possible diameter.
Note that cow paths do not connect just because they cross each other; they only connect at listed points.
The input contains the pastures, their locations, and a symmetric "adjacency" matrix that tells whether pastures are connected by cow paths. Pastures are not considered to be connected to themselves. Here's one annotated adjacency list for the pasture {A,B,C,D,E,F,G,H} as shown above:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
Other equivalent adjacency lists might permute the rows and columns by using some order other than alphabetical to show the point connections. The input data contains no names for the points.
The input will contain at least two pastures that are not connected by any sequence of cow paths.
Find a way to connect exactly two pastures in the input with a cow path so that the new combined field has the smallest possible diameter of any possible pair of connected pastures. Output that smallest possible diameter.
PROGRAM NAME: cowtour
INPUT FORMAT
Line 1: An integer, N (1 <= N <= 150), the number of pastures
Line 2-N+1: Two integers, X and Y (0 <= X ,Y<= 100000), that denote that X,Y grid location of the pastures; all input pastures are unique.
Line N+2-2*N+1: lines, each containing N digits (0 or 1) that represent the adjacency matrix as described above, where the rows' and columns' indices are in order of the points just listed.
SAMPLE INPUT (file cowtour.in)
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT FORMAT
The output consists of a single line with the diameter of the newly joined pastures. Print the answer to exactly six decimal places. Do not perform any special rounding on your output.
SAMPLE OUTPUT (file cowtour.out)
22.071068
描述
农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个牧区通过任何路径都不连通。这样,Farmer John就有多个牧场了。
John想在农场里添加一条路径(注意,恰好一条)。对这条路径有以下限制:
一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场,牧区用“*”表示,路径用直线表示。每一个牧区都有自己的坐标:
(15,15) (20,15)
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
(10,10) (15,10) (20,10)
这个牧场的直径大约是12.07106, 最远的两个牧区是A和E,它们之间的最短路径是A-B-E。
这里是另一个牧场:
*F(30,15)
/
_/
_/
/
*------*
G H
(25,10) (30,10)
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区,然后用一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。
注意,如果两条路径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交,我们才认为它们是连通的。
输入文件包括牧区、它们各自的坐标,还有一个如下的对称邻接矩阵:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入文件至少包括两个不连通的牧区。
请编程找出一条连接两个不同牧场的路径,使得连上这条路径后,这个更大的新牧场有最小的直径。
格式
PROGRAM NAME: cowtour
INPUT FORMAT:
(file cowtour.in)
第1行: 一个整数N (1 <= N <= 150), 表示牧区数
第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个牧区的坐标。注意每个 牧区的坐标都是不一样的。
第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。
OUTPUT FORMAT:
(file cowtour.out)
只有一行,包括一个实数,表示所求直径。数字保留六位小数。
SAMPLE INPUT
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
SAMPLE OUTPUT
22.071068
====================== 华丽的分割线 ======================
实在是不会写, 直接看标程,, 但是标程也好难看懂` 思路是大致是
point是一个结构体, point[i] 表示第i个牧区的坐标:
用一个数组dis[i][j] 表示从第i个牧区到第j个牧区的最短距离(直接间接的都包括在内.), 然后还有一个数组fie[i]表示第i个牧区所在的牧场编号. diam[i]表示在fie[i]这个牧场里距离i最远的牧区之间的距离是多少.. 也就是说diam[i]表示的是同一个牧场中, 距离i最远的牧区和i之间的距离. fdiam[i] 表示编号为i的牧场的直径.
代码:
Farmer John has a number of pastures on his farm. Cow paths connect some pastures with certain other pastures, forming a field. But, at the present time, you can find at least two pastures that cannot be connected by any sequence of cow paths, thus partitioning Farmer John's farm into multiple fields.
Farmer John would like add a single a cow path between one pair of pastures using the constraints below.
A field's `diameter' is defined to be the largest distance of all the shortest walks between any pair of pastures in the field. Consider the field below with five pastures, located at the points shown, and cow paths marked by lines:
15,15 20,15
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
10,10 15,10 20,10
The `diameter' of this field is approximately 12.07106, since the longest of the set of shortest paths between pairs of pastures is the path from A to E (which includes the point set {A,B,E}). No other pair of pastures in this field is farther apart when connected by an optimal sequence of cow paths.
Suppose another field on the same plane is connected by cow paths as follows:
*F 30,15
/
_/
_/
/
*------
G H
25,10 30,10
In the scenario of just two fields on his farm, Farmer John would add a cow path between a point in each of these two fields (namely point sets {A,B,C,D,E} and {F,G,H}) so that the joined set of pastures {A,B,C,D,E,F,G,H} has the smallest possible diameter.
Note that cow paths do not connect just because they cross each other; they only connect at listed points.
The input contains the pastures, their locations, and a symmetric "adjacency" matrix that tells whether pastures are connected by cow paths. Pastures are not considered to be connected to themselves. Here's one annotated adjacency list for the pasture {A,B,C,D,E,F,G,H} as shown above:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
Other equivalent adjacency lists might permute the rows and columns by using some order other than alphabetical to show the point connections. The input data contains no names for the points.
The input will contain at least two pastures that are not connected by any sequence of cow paths.
Find a way to connect exactly two pastures in the input with a cow path so that the new combined field has the smallest possible diameter of any possible pair of connected pastures. Output that smallest possible diameter.
PROGRAM NAME: cowtour
INPUT FORMAT
Line 1: An integer, N (1 <= N <= 150), the number of pastures
Line 2-N+1: Two integers, X and Y (0 <= X ,Y<= 100000), that denote that X,Y grid location of the pastures; all input pastures are unique.
Line N+2-2*N+1: lines, each containing N digits (0 or 1) that represent the adjacency matrix as described above, where the rows' and columns' indices are in order of the points just listed.
SAMPLE INPUT (file cowtour.in)
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT FORMAT
The output consists of a single line with the diameter of the newly joined pastures. Print the answer to exactly six decimal places. Do not perform any special rounding on your output.
SAMPLE OUTPUT (file cowtour.out)
22.071068
描述
农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个牧区通过任何路径都不连通。这样,Farmer John就有多个牧场了。
John想在农场里添加一条路径(注意,恰好一条)。对这条路径有以下限制:
一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场,牧区用“*”表示,路径用直线表示。每一个牧区都有自己的坐标:
(15,15) (20,15)
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
(10,10) (15,10) (20,10)
这个牧场的直径大约是12.07106, 最远的两个牧区是A和E,它们之间的最短路径是A-B-E。
这里是另一个牧场:
*F(30,15)
/
_/
_/
/
*------*
G H
(25,10) (30,10)
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区,然后用一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。
注意,如果两条路径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交,我们才认为它们是连通的。
输入文件包括牧区、它们各自的坐标,还有一个如下的对称邻接矩阵:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入文件至少包括两个不连通的牧区。
请编程找出一条连接两个不同牧场的路径,使得连上这条路径后,这个更大的新牧场有最小的直径。
格式
PROGRAM NAME: cowtour
INPUT FORMAT:
(file cowtour.in)
第1行: 一个整数N (1 <= N <= 150), 表示牧区数
第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个牧区的坐标。注意每个 牧区的坐标都是不一样的。
第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。
OUTPUT FORMAT:
(file cowtour.out)
只有一行,包括一个实数,表示所求直径。数字保留六位小数。
SAMPLE INPUT
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
SAMPLE OUTPUT
22.071068
====================== 华丽的分割线 ======================
实在是不会写, 直接看标程,, 但是标程也好难看懂` 思路是大致是
point是一个结构体, point[i] 表示第i个牧区的坐标:
引用
struct point{
int x, y;
}point[MAX];
int x, y;
}point[MAX];
用一个数组dis[i][j] 表示从第i个牧区到第j个牧区的最短距离(直接间接的都包括在内.), 然后还有一个数组fie[i]表示第i个牧区所在的牧场编号. diam[i]表示在fie[i]这个牧场里距离i最远的牧区之间的距离是多少.. 也就是说diam[i]表示的是同一个牧场中, 距离i最远的牧区和i之间的距离. fdiam[i] 表示编号为i的牧场的直径.
代码:
/* LANG: C ID: zqy11001 PROG: cowtour */ #include <stdio.h> #define INF (1e5) #define MAX (150) #define getint(i) scanf("%d", &i) struct point{ int x, y; }point[MAX]; double dis[MAX][MAX]; double diam[MAX]; double fdiam[MAX]; int fie[MAX]; int n; double getdis(int i, int j) { struct point *a, *b; a = &point[i]; b = &point[j]; return sqrt((double)(a->x - b->x)* (a->x - b->x) + (double)(a->y - b->y)* (a->y - b->y)); } void mark(int i, int m) { int j; if(fie[i] != 0){ return ; } fie[i] = m; for(j = 0; j < n; j++){ if(dis[i][j] < INF){ mark(j, m); } } } int main(void) { int i, j, k; int c, now = 1; double t, max; freopen("cowtour.in", "r", stdin); freopen("cowtour.out", "w", stdout); getint(n); for(i = 0; i < n; i++){ getint(point[i].x); getint(point[i].y); } for(i = 0; i < n; i++){ getchar(); for(j = 0; j < n; j++){ c = getchar(); if(i == j){ dis[i][j] = 0; }else if(c == '0'){ dis[i][j] = INF; }else{ dis[i][j] = getdis(i, j); } } } for(i = 0; i < n; i++){ if(fie[i] == 0){ mark(i, now++); } } for(k = 0; k < n; k++) for(i = 0; i < n; i++) for(j = 0; j < n; j++){ if(dis[i][j] > dis[i][k] + dis[k][j]){ dis[i][j] = dis[i][k] + dis[k][j]; } } for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ if(diam[i] < dis[i][j] && dis[i][j] < INF){ diam[i] = dis[i][j]; } } if(fdiam[fie[i]] < diam[i]){ fdiam[fie[i]] = diam[i]; } } max = INF; for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ if(fie[i] == fie[j]){ continue; } t = diam[i] + diam[j] + getdis(i, j); if(t < fdiam[fie[i]]){ t = fdiam[fie[i]]; } if(t < fdiam[fie[j]]){ t = fdiam[fie[j]]; } if(t < max){ max = t; } } } printf("%.6lf\n", max); return 0; }
发表评论
-
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 1262/* LANG: C ID: zqynux11 PROG ... -
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 805解释什么的就算了吧,, /* LANG: C ID: ... -
重做 USACO 1.1 贪婪的送礼者
2010-03-31 18:58 1204这题的话, 我用的是个结构体, 记录各个人.. 我错了的地 ... -
重做 USACO 1.1 你的飞碟在这儿
2010-03-31 18:56 843不解释了.. /* LANG: C ID: zqynu ... -
USACO 3.1 Shaping Regions 形成的区域
2010-03-30 20:01 1491这题二话不说, 用map[i][j]表示坐标为i, j的点 ... -
USACO 3.1 Humble Numbers 丑数
2010-03-28 15:31 1438从这一题开始,, 以后题目我就不贴上来了... 自己去看吧 ... -
USACO 3.1 Score Inflation 总分
2010-03-27 20:19 798Score Inflation The more point ... -
USA 3.1 Agri-Net 最短网络
2010-03-27 20:14 837Agri-Net Russ Cox Farmer John ... -
USACO 2.4 Fractions to Decimals 分数化小数
2010-03-27 15:47 1242Fractions to Decimals Write a ... -
USACO 2.4 Bessie Come Home 回家
2010-03-27 13:01 990Bessie Come Home Kolstad & ... -
USACO 2.4 Overfencing 穿越栅栏
2010-03-25 18:18 930USACO 2.4 Overfencing 穿越栅栏 Over ... -
USACO 2.4 The Tamworth Two 两只塔姆沃斯牛
2010-03-23 22:05 1167The Tamworth Two BIO '98 - Rich ... -
USACO 2.3 Controlling Companies 控制公司
2010-03-23 22:00 1417Controlling Companies Some com ... -
USACO 1.1 Broken Necklace 破碎的项链
2010-03-22 18:04 2073Broken Necklace You have a neck ... -
USACO 2.3 Money Systems 货币系统
2010-03-22 13:31 947Money Systems The cows have no ... -
USACO 2.3 Cow Pedigrees 奶牛家谱
2010-03-21 15:02 1406Farmer John is considering purc ... -
USACO 2.3 Zero Sum 零的算式和
2010-03-20 14:30 1755Zero Sum Consider the sequence ... -
USACO Longest Prefix最长前缀
2010-03-17 12:28 1397Longest Prefix IOI'96 The stru ... -
vijos 谁拿了最多奖学金
2010-03-17 12:25 1063描述 Description 某校的惯例是在每 ... -
USACO 2.2 Subset Sums集合
2010-03-16 12:18 1420USACO 2.2 Subset Sums集合 For ...
相关推荐
usaco2.4解题报告1
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
适合USACO的Java选手参考
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO题集及答案
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
以上代码是大学里的大牛所写的,正确性没有问题。而且容易被广大初学数据结构的菜鸟看懂。
USACO历年比赛测试数据:2003年 方便大家测试
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
USACO全部译题 USACO Training Program Gateway
内含USACO全部测试数据,绝对全
usaco traning的全部数据 才要3分
USACO所有题目的题解 NOCOW整理版
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
USACO历年比赛测试数据:2006年方便大家测试