題目大意如下
在一個二維坐標系中，有n個城市，坐標給出來了，然後有p個士兵要去占領這n個城市，但是路上有m個路障，都是線段，士兵不能越過路障前進。
每個士兵都有相同容量大小的一個干糧袋，每到一個城市他就能補充滿自己的干糧袋。中途走路時走一個單位長度就消耗一個單位的干糧。
現在問的是這些個干糧袋最小的容量是多少，前提是保證p個士兵能占領完這n個城市，城市被占領順序也是題目給好的，必須遵守
思路：P個士兵占領n個城市，可以看成p個士兵走出了p個路徑，覆蓋了所有的點。 但是題目沒要求每個士兵都必須去占領。 也就是只要最小路徑覆蓋小於等於p個就代表所有的城市能被p個士兵去占領了。
最小路徑覆蓋的要求之一就是有向，無環，在題目中的體現就是城市被占領時必須有順序。
這就符合一個拓撲序列了。所以就可以進行最小路徑覆蓋
然後整體的步驟就是，剛開始把各個點之間的距離先算出來，因為有障礙，所以必須把這些線段的兩個端點都加入到點集中一塊算，預處理兩點距離時，就看兩點之間有沒有線段擋著，擋著就先按不可達算，注意處理線段交的時候端點相交不要管，因為還是可以過去。 沒擋著就按照直線距離算。 然後floyd處理一下，任意兩點之間的距離就算出來了
算出來後我們就要求干糧袋的容量了，一般的方法就是二分求可行性。
對於二分的一個值，我們就建立一遍圖，任意兩點的距離不大於這個值才可以連邊。
當然注意我們是按照題目中給的那個占領順序，前邊的可以向後邊的連邊，反之不能
然後求路徑覆蓋。判斷是否可行
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define eps 1e-8
#define MAXN 333
#define INF 1111111111
using namespace std;
typedef double TYPE;
struct POINT
{
TYPE x;
TYPE y;
POINT() : x(0), y(0) {};
POINT(TYPE _x_, TYPE _y_) : x(_x_), y(_y_) {};
bool operator == (const POINT &p)const
{
return (fabs(x - p.x) < eps && fabs(y - p.y) < eps);
}
}p[MAXN];
TYPE Distance(const POINT & a, const POINT & b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct SEG
{
POINT a; //起點
POINT b; //終點
SEG() {};
SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};
bool operator == (const SEG &p)const
{
return (p.a == a && p.b == b) || (p.b == a && p.a == b);
}
}seg[MAXN];
TYPE Cross(const POINT & a, const POINT & b, const POINT & o)
{
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool IsIntersect(const SEG & u, const SEG & v)
{
return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) > 0) &&
(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) > 0) &&
(max(u.a.x, u.b.x) > min(v.a.x, v.b.x)) &&
(max(v.a.x, v.b.x) > min(u.a.x, u.b.x)) &&
(max(u.a.y, u.b.y) > min(v.a.y, v.b.y)) &&
(max(v.a.y, v.b.y) > min(u.a.y, u.b.y));
}
int seq[MAXN];
struct node
{
int v, next;
}edge[MAXN * MAXN];
int e, head[MAXN], mark[MAXN], cx[MAXN], cy[MAXN], n, m, so;
double dis[MAXN][MAXN];
void insert(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
int path(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(!mark[v])
{
mark[v] = 1;
if(cy[v] == -1 || path(cy[v]))
{
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int gao()
{
int ans = 0;
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
for(int i = 1; i <= n; i++)
{
memset(mark, 0, sizeof(mark));
ans += path(i);
}
return ans;
}
void floyd(int n)
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
bool ok(double mid)
{
e = 0;
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if(dis[seq[i]][seq[j]] <= mid)
insert(seq[i], seq[j] + n);
int x = gao();
if(n - x <= so) return true;
return false;
}
void slove()
{
double l = 0, r = INF;
double ans = -1;
while(r - l > eps)
{
double mid = (l + r) / 2;
if(ok(mid)) {ans = mid; r = mid;}
else l = mid;
}
printf("%.2f\n", ans);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &m, &so);
for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
for(int i = 1; i <= m; i++)
{
scanf("%lf%lf%lf%lf", &seg[i].a.x, &seg[i].a.y, &seg[i].b.x, &seg[i].b.y);
p[n + i * 2 - 1] = seg[i].a;
p[n + i * 2] = seg[i].b;
}
for(int i = 1; i <= n; i++) scanf("%d", &seq[i]);
for(int i = 1; i <= n + m * 2; i++)
for(int j = 1; j <= n + m * 2; j++)
{
if(i == j) {dis[i][j] = 0; continue;}
int flag = false;
for(int k = 1; k <= m; k++)
{
if(seg[k] == SEG(p[i], p[j])) continue;
if(IsIntersect(seg[k], SEG(p[i], p[j])))
{
flag = true;
break;
}
}
if(flag) dis[i][j] = INF;
else dis[i][j] = Distance(p[i], p[j]);
}
floyd(n + m * 2);
slove();
}
return 0;
}
