hdu4606:http://acm.hdu.edu.cn/showproblem.php?pid=4606
题意：在一个二维坐标系中，有n个城市，坐标给出来了，然后有p个士兵要去占领这n个城市，但是路上有m个路障，都是线段，士兵不能越过路障前进。
每个士兵都有相同容量大小的一个干粮袋，每到一个城市他就能补充满自己的干粮袋。中途走路时走一个单位长度就消耗一个单位的干粮。
现在问的是这些个干粮袋最小的容量是多少，前提是保证p个士兵能占领完这n个城市，城市被占领顺序也是题目给好的，必须遵守。
题解：这一题是一道很好的综合题。首先一点，就是求出任意两个城市的最短距离。这个也是我今天学到的知识。我们可以把障碍的端点当做2个点，如果城市i和城市j之间没有障碍的话，那么i，j之间的距离就可以直接算出。如果有障碍的话，就只能绕过障碍的端点来求。怎么求呢？只要把端点当做路径上的点就可以了，然后用floyd过一遍即可。这里，要用到判断两条线段是否相交的。然后可以联想到的是最小点覆盖。但是这里的是最小点覆盖小于p都是满足的。所以接下来可以二分枚举长度，找到最小额满足条件的长度。用到二分以及二分图的最大匹配。因为最小点覆盖==点数--二分图的最大匹配。还有一个就序列，这也是要考虑。这里只哎哟我们建图的时候，让前面的序列指向后面的序列就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const double inf=1000000000.0;
int n,m,p;
int seq[],cy[];
double g[][];
bool key[][],visit[];
struct point{
double x,y;
}dian[];
struct Node{
point a;
point b;
}xian[];
double dis(int a,int b){
return sqrt((dian[a].x-dian[b].x)*(dian[a].x-dian[b].x)+(dian[a].y-dian[b].y)*(dian[a].y-dian[b].y)); }
double Cross( point a, point b, point o){
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool IsIntersect( Node u, Node v){
return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) > ) &&
(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) > ) &&
(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));
} bool judge(int a,int b){
for(int i=;i<=m;i++){
if((a+-n)/==i&&(b+-n)/==i)continue;
Node temp;temp.a=dian[a];temp.b=dian[b];
if(IsIntersect(temp,xian[i]))
return false;
}
return true;
}
int path(int u){
for(int i=;i<=n;i++){
if(!visit[i]&&key[u][i]){
visit[i]=;
if(cy[i]==-||path(cy[i])){
cy[i]=u;
return ;
}
}
}
return ;
}
int maxmatch(){
memset(cy,-,sizeof(cy));
int res=;
for(int i=;i<=n;i++){
memset(visit,,sizeof(visit));
res+=path(i);
}
return res;
}
bool task(double mid){
memset(key,,sizeof(key));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(g[i][j]<=mid&&seq[i]<seq[j])
key[i][j]=;
}
int as=maxmatch();
if(n-as<=p)return true;
else return false;
} double solve(){
double l=,r=inf,ans=;
while(abs(l-r)>0.0000001){
double mid=(l+r)/;
if(task(mid)){
ans=mid;
r=mid;
}
else
l=mid;
}
return ans;
}
int temp;
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&n,&m,&p);
memset(g,,sizeof(g));
for(int i=;i<=n;i++){
scanf("%lf%lf",&dian[i].x,&dian[i].y);
}
for(int i=;i<=m;i++){
scanf("%lf %lf",&xian[i].a.x,&xian[i].a.y);
dian[i*+n-].x=xian[i].a.x;
dian[i*+n-].y=xian[i].a.y;
scanf("%lf %lf",&xian[i].b.x,&xian[i].b.y);
dian[i*+n].x=xian[i].b.x;
dian[i*+n].y=xian[i].b.y;
}
memset(seq,,sizeof(seq));
for(int i=;i<=n;i++){
scanf("%d",&temp);
seq[temp]=i;
}
for(int i=;i<=n+*m;i++){
for(int j=;j<=n+*m;j++){
if(j==i)continue;
if(judge(i,j)){
g[i][j]=dis(i,j);
}
else
g[i][j]=inf;
}
g[i][i]=inf;
}
for(int k=;k<=n+*m;k++)
for(int i=;i<=n+*m;i++)
for(int j=;j<=n+*m;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
double ans=;
ans=solve();
printf("%.2f\n",ans);
}
}