灵魂宝石 BZOJ 2663
2018-06-17 23:26:58来源:未知 阅读 ()
灵魂宝石
【问题描述】
“作为你们本体的灵魂,为了能够更好的运用魔法,被赋予了既小巧又安全的外形”
我们知道,魔法少女的生命被存放于一个称为灵魂宝石(Soul Gem)的装置内。而有时,当灵魂宝石与躯体的距离较远时,魔法少女就无法控制自己的躯体了。在传说中,魔法少女Abel仅通过推理就得到了这个现象的一般法则,被称为Abel定理:存在宇宙常量R(是一个非负实数,或正无穷),被称为灵魂宝石常量,量纲为空间度量(即:长度)。如果某个魔法少女的灵魂宝石与她的躯体的距离严格超过R,则她一定无法控制自己的躯体;如果这个距离严格小于R,则她一定可以控制自己的躯体。(这里的距离指平面的 Euclid距离。)
注意:该定理不能预言距离刚好为R的情形。可能存在魔法少女A和B,她们离自己的灵魂宝石的距离都恰好为R,但是A可以控制自己的躯体,而B不可以。
现在这个世界上再也没有魔法少女了,但是我们却对这个宇宙常量感兴趣。我们只能通过之前的世界遗留下来的数据来确定这个常量的范围了。
每一组数据包含以下信息:
一共有N个魔法少女及她们的灵魂宝石,分别编号为1-N。
这N个魔法少女所在的位置是(Xi, Yi)。
这N个灵魂宝石所在的位置是(xi, yi)。
此时恰好有 K个魔法少女能够控制自己的躯体。
1.我们认为这个世界是二维的 Euclid 空间。
2.魔法少女与灵魂宝石之间的对应关系是未知的。
3.我们不知道是具体是哪 K个魔法少女能够控制自己的躯体。
根据以上信息,你需要确定灵魂宝石常量 R可能的最小值 Rmin 和最大值Rmax。
【输入格式】
第一行包两个整数:N、K。
接下来N行,每行包含两个整数:Xi,Yi,由空格隔开。
再接下来N行,每行包含两个整数:xi,yi,由空格隔开。
【输出格式】
输出两个量:Rmin、Rmax,中间用空格隔开。
Rmin 一定是一个非负实数,四舍五入到小数点后两位。
Rmax 可能是非负实数,或者是正无穷:
如果是非负实数,四舍五入到小数点后两位;
如果是正无穷,输出“+INF”(不包含引号)。
【输入样例】
2 1
1 0
4 0
0 0
4 4
【输出样例】
1.00 5.00
【数据范围】
对于100%的数据:
1 ≤ N ≤ 50,0 ≤ K ≤ N,-1000 ≤ xi,yi,Xi,Yi ≤ 1000。
题解:
题意:对于n个人与n个宝石,每个人需要各自匹配一1颗与其距离小于k的宝石,距离等于k的宝石可以自由选择是否匹配,求k的最小值与最大值
那么最小值可以很容易想到二分,连接所有距离小于k的边,用二分图匹配检验,则为用最大匹配数求最小值
然而最大值并不能直接像最小值一样求解,因为二分图求的是最大匹配,这一点模拟样例就可以得到
于是考虑一点小小的转化
最大值的检验中,我们将距离大于等于k的边相连
那么二分图匹配跑出的结果就是最大不匹配数
总个数减去最大不匹配数即为最小匹配数
利用最小匹配数就能求出最大值
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 struct shape
9 {
10 double x, y;
11 };
12 int n, k;
13 double l, r;
14 double ans;
15 int my[233];
16 shape a[233];
17 bool vis[233];
18 int tot, to[10233], nex[10233], fir[233];
19 inline double Dis(shape x, shape y)
20 {
21 return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
22 }
23 inline void Ins(int x, int y)
24 {
25 nex[++tot] = fir[x];
26 fir[x] = tot;
27 to[tot] = y;
28 }
29 bool Find(int u)
30 {
31 for(int i = fir[u]; i; i = nex[i])
32 {
33 int v = to[i];
34 if(!vis[v])
35 {
36 vis[v] = true;
37 if(!my[v] || Find(my[v]))
38 {
39 my[v] = u;
40 return true;
41 }
42 }
43 }
44 return false;
45 }
46 inline bool Checkmi(double x)
47 {
48 tot = 0;
49 for(int i = 1; i <= n; ++i) my[i + n] = fir[i] = 0;
50 for(int i = 1; i <= n; ++i)
51 for(int j = n + 1; j <= n + n; ++j)
52 if(Dis(a[i], a[j]) <= x)
53 Ins(i, j);
54 int sum = 0;
55 for(int i = 1; i <= n; ++i)
56 {
57 for(int j = 1; j <= n; ++j)
58 vis[j + n] = false;
59 if(Find(i)) ++sum;
60 }
61 if(sum < k) return true;
62 return false;
63 }
64 inline bool Checkma(double x)
65 {
66 tot = 0;
67 for(int i = 1; i <= n; ++i) my[i + n] = fir[i] = 0;
68 for(int i = 1; i <= n; ++i)
69 for(int j = n + 1; j <= n + n; ++j)
70 if(Dis(a[i], a[j]) >= x)
71 Ins(i, j);
72 int sum = 0;
73 for(int i = 1; i <= n; ++i)
74 {
75 for(int j = 1; j <= n; ++j)
76 vis[j + n] = false;
77 if(Find(i)) ++sum;
78 }
79 if(sum < n - k) return false;
80 return true;
81 }
82 int main()
83 {
84 // freopen("soulgem.in", "r", stdin), freopen("soulgem.out", "w", stdout);
85 scanf("%d%d", &n, &k);
86 for(int i = 1; i <= n + n; ++i)
87 scanf("%lf %lf", &a[i].x, &a[i].y);
88 l = 0, r = 3666;
89 for(int i = 1; i <= 38; ++i)
90 {
91 double mi = (l + r) / 2.0;
92 if(Checkmi(mi)) l = mi;
93 else ans = mi, r = mi;
94 }
95 printf("%.2lf ", ans);
96 ans = 3666;
97 l = 0, r = 3666;
98 for(int i = 1; i <= 38; ++i)
99 {
100 double mi = (l + r) / 2.0;
101 if(Checkma(mi)) ans = mi, l = mi;
102 else r = mi;
103 }
104 if(fabs(ans - 3666) <= 0.001) printf("+INF");
105 else printf("%.2lf", ans);
106 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash