思路：将所有的直线的两个端点和城市混在一起，将能直接到达的两个点连线，求一次floyd最短路径。二分枚举bag容量，然后按给的要先后占领的城市由前向后，把能到一步到达的建一条边。然后求一次最小路径覆盖，就是最少需要多少个士兵才能全部占领，跟给出的p值进行比较。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define Maxn 510 #define Maxm Maxn*Maxn #define eps 1e-6 #define inf 100000000 using namespace std; int match[Maxn],vi[Maxn],graphic[Maxn][Maxn],n,m,p,list[Maxn]; double dis[Maxn][Maxn]; struct Point{ double x,y; }city[Maxn*10]; struct Edge{ Point a,b; }edge[Maxn]; void init() { int i,j; memset(vi,0,sizeof(vi)); memset(match,-1,sizeof(match)); memset(graphic,0,sizeof(graphic)); for(i=1;i<=500;i++) for(j=1;j<=500;j++) dis[i][j]=inf; } double multi(Point p0, Point p1, Point p2)//j计算差乘 { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);} double Dis(Point &a,Point &b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} bool is_cross(Point s1,Point e1,Point s2,Point e2)//判断线段是否相交（非规范相交） { return multi(s1,e1,s2)*multi(s1,e1,e2) < -eps && multi(s2,e2,s1)*multi(s2,e2,e1) < -eps; } int dfs(int u) { int i,j; for(i=1;i<=n;i++) { if(!vi[i]&&graphic[u][i]) { vi[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0; } int maxmatch() { int i,j; int ans=0; memset(match,-1,sizeof(match)); for(i=1;i<=n;i++) { memset(vi,0,sizeof(vi)); if(dfs(i)) ans++; } return n-ans; } int main() { int t,i,j,e,k; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&p); init(); for(i=1;i<=n;i++) scanf("%lf %lf",&city[i].x,&city[i].y); e=n; for(i=1;i<=m;i++) { scanf("%lf%lf%lf%lf",&edge[i].a.x,&edge[i].a.y,&edge[i].b.x,&edge[i].b.y); city[++e].x=edge[i].a.x,city[e].y=edge[i].a.y;city[++e].x=edge[i].b.x,city[e].y=edge[i].b.y; } for(i=1;i<=n;i++) scanf("%d",list+i); int flag=0; for(i=1;i<e;i++)//将能直线到达的点建边 { for(j=i+1;j<=e;j++) { flag=0; for(k=1;k<=m;k++) { if(is_cross(city[i],city[j],edge[k].a,edge[k].b)) { flag=1; break; } } if(!flag) dis[i][j]=dis[j][i]=Dis(city[i],city[j]); } } double Max=0; for(k=1;k<=e;k++)//求所有点的最短路径 for(i=1;i<=e;i++) for(j=1;j<=e;j++) { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dis[i][j]!=inf) Max=max(Max,dis[i][j]); double l,r,mid; l=0,r=Max; int temp; while(r-l>eps)//二分枚举bag容量 { mid=(l+r)/2; memset(graphic,0,sizeof(graphic)); for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { if(dis[list[i]][list[j]]<=mid) { graphic[list[i]][list[j]]=1; } } temp=maxmatch(); if(temp>p) l=mid; else r=mid; } printf("%.2lf ",r); } return 0; }