靈魂寶石（1s 128MB）soulgem 【問題描述】 “作為你們本體的靈魂，為了能夠更好的運用魔法，被賦予了既小巧又安全的外形······” 我們知道，魔法少女的生命被存放於一個稱為靈魂寶石（Soul Gem）的裝置內。而有時，當靈魂寶石與軀體的距離較遠時，魔法少女就無法控制自己的軀體了。 在傳 ...
靈魂寶石（1s 128MB）soulgem
【問題描述】
“作為你們本體的靈魂，為了能夠更好的運用魔法，被賦予了既小巧又安全的外形······”
我們知道，魔法少女的生命被存放於一個稱為靈魂寶石（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。
題解：
主要演算法：二分圖匹配 or 網路流；二分；
題意：對於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 }
