首页 > 代码库 > Occupy Cities
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 else120 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("%.2f\n",ans);131 }132 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。