Occupy Cities

65 阅读 0 评论 43 点赞

我是靠谱客的博主俭朴鸡翅，最近开发中收集的这篇文章主要介绍Occupy Cities，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

hdu4606:http://acm.hdu.edu.cn/showproblem.php?pid=4606

题意：在一个二维坐标系中，有n个城市，坐标给出来了，然后有p个士兵要去占领这n个城市，但是路上有m个路障，都是线段，士兵不能越过路障前进。

每个士兵都有相同容量大小的一个干粮袋，每到一个城市他就能补充满自己的干粮袋。中途走路时走一个单位长度就消耗一个单位的干粮。

现在问的是这些个干粮袋最小的容量是多少，前提是保证p个士兵能占领完这n个城市，城市被占领顺序也是题目给好的，必须遵守。

题解：这一题是一道很好的综合题。首先一点，就是求出任意两个城市的最短距离。这个也是我今天学到的知识。我们可以把障碍的端点当做2个点，如果城市i和城市j之间没有障碍的话，那么i，j之间的距离就可以直接算出。如果有障碍的话，就只能绕过障碍的端点来求。怎么求呢？只要把端点当做路径上的点就可以了，然后用floyd过一遍即可。这里，要用到判断两条线段是否相交的。然后可以联想到的是最小点覆盖。但是这里的是最小点覆盖小于p都是满足的。所以接下来可以二分枚举长度，找到最小额满足条件的长度。用到二分以及二分图的最大匹配。因为最小点覆盖==点数--二分图的最大匹配。还有一个就序列，这也是要考虑。这里只哎哟我们建图的时候，让前面的序列指向后面的序列就可以了。


1 #include<cstdio>

2 #include<cstring>

3 #include<algorithm>

4 #include<iostream>

5 #include<cmath>

6 using namespace std;

7 const double inf=1000000000.0;

8 int n,m,p;

9 int seq[600],cy[600];
 10 double g[600][600];
 11 bool key[600][600],visit[600];
 12 struct point{
 13
double x,y;
 14 }dian[602];
 15 struct Node{
 16 
point a;
 17 
point b;
 18 }xian[602];
 19 double dis(int a,int b){
 20
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));
 21
 22 }
 23 double Cross( point a,
point b,
point
o){
 24
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
 25 }
 26 bool IsIntersect( Node u, Node v){
 27
return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) > 0) &&
 28
(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) > 0) &&
 29
(max(u.a.x, u.b.x) > min(v.a.x, v.b.x)) &&
 30
(max(v.a.x, v.b.x) > min(u.a.x, u.b.x)) &&
 31
(max(u.a.y, u.b.y) > min(v.a.y, v.b.y)) &&
 32
(max(v.a.y, v.b.y) > min(u.a.y, u.b.y));
 33 }
 34
 35 bool judge(int a,int b){
 36
for(int i=1;i<=m;i++){
 37
if((a+1-n)/2==i&&(b+1-n)/2==i)continue;
 38
Node temp;temp.a=dian[a];temp.b=dian[b];
 39
if(IsIntersect(temp,xian[i]))
 40
return false;
 41 
}
 42
return true;
 43 }
 44 int path(int u){
 45
for(int i=1;i<=n;i++){
 46
if(!visit[i]&&key[u][i]){
 47
visit[i]=1;
 48
if(cy[i]==-1||path(cy[i])){
 49
cy[i]=u;
 50
return 1;
 51 
}
 52 
}
 53 
}
 54
return 0;
 55 }
 56 int maxmatch(){
 57
memset(cy,-1,sizeof(cy));
 58
int res=0;
 59
for(int i=1;i<=n;i++){
 60
memset(visit,0,sizeof(visit));
 61
res+=path(i);
 62 
}
 63
return res;
 64 }
 65 bool task(double mid){
 66
memset(key,0,sizeof(key));
 67
for(int i=1;i<=n;i++)
 68
for(int j=1;j<=n;j++){
 69
if(g[i][j]<=mid&&seq[i]<seq[j])
 70
key[i][j]=1;
 71 
}
 72
int as=maxmatch();
 73
if(n-as<=p)return true;
 74
else return false;
 75 }
 76
 77 double solve(){
 78
double l=0,r=inf,ans=0;
 79
while(abs(l-r)>0.0000001){
 80
double mid=(l+r)/2;
 81
if(task(mid)){
 82
ans=mid;
 83
r=mid;
 84 
}
 85
else
 86
l=mid;
 87 
}
 88
return ans;
 89 }
 90 int temp;
 91 int main(){
 92
int cas;
 93
scanf("%d",&cas);
 94
while(cas--){
 95
scanf("%d%d%d",&n,&m,&p);
 96
memset(g,0,sizeof(g));
 97
for(int i=1;i<=n;i++){
 98
scanf("%lf%lf",&dian[i].x,&dian[i].y);
 99 
}
100
for(int i=1;i<=m;i++){
101
scanf("%lf %lf",&xian[i].a.x,&xian[i].a.y);
102
dian[i*2+n-1].x=xian[i].a.x;
103
dian[i*2+n-1].y=xian[i].a.y;
104
scanf("%lf %lf",&xian[i].b.x,&xian[i].b.y);
105
dian[i*2+n].x=xian[i].b.x;
106
dian[i*2+n].y=xian[i].b.y;
107 
}
108
memset(seq,0,sizeof(seq));
109
for(int i=1;i<=n;i++){
110
scanf("%d",&temp);
111
seq[temp]=i;
112 
}
113
for(int i=1;i<=n+2*m;i++){
114
for(int j=1;j<=n+2*m;j++){
115
if(j==i)continue;
116
if(judge(i,j)){
117
g[i][j]=dis(i,j);
118 
}
119
else
120
g[i][j]=inf;
121 
}
122
g[i][i]=inf;
123 
}
124
for(int k=1;k<=n+2*m;k++)
125
for(int i=1;i<=n+2*m;i++)
126
for(int j=1;j<=n+2*m;j++)
127
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
128
double ans=0;
129
ans=solve();
130
printf("%.2fn",ans);
131 
}
132 }