首页 > 代码库 > 【BZOJ 1027】 (凸包+floyd求最小环)
【BZOJ 1027】 (凸包+floyd求最小环)
【题意】
某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的
原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝
锡比重为用户所需要的比重。 现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能
够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。
【分析】
只要考虑前两个物质的比例,因为加起来等于1。
如果你看过zoj3154,就会知道这题的模型,用二元组表示合金(x1,y1)(x2,y2),他们能混合成的合金就是线段(x1,y1)->(x2,y2),
那么一堆点组成的合金就是那些点组成的凸包面积。
然后看了po姐的下一步转化,就是若点i->j的一侧包含了所有B点集,那么i->j连一条边,然后floyd求最小环即可。
有一个地方我一开始错了:若B中有一个点在i->j上,要判断是不是线段上的,若只是直线上,也是不能组成的。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 510 8 #define INF 0x7fffffff 9 10 int m,n; 11 12 int mymin(int x,int y) {return x<y?x:y;} 13 14 const double eps=0.0001; 15 16 struct node 17 { 18 double x,y; 19 }; 20 node t[Maxn*2]; 21 22 node operator - (node x,node y) 23 { 24 node P; 25 P.x=x.x-y.x;P.y=x.y-y.y; 26 return P; 27 // return node{x.x-y.x,x.y-y.y}; 28 } 29 30 double myabs(double x) {return x>0?x:-x;} 31 32 bool operator != (node x,node y) {return myabs(x.x-y.x)>eps||myabs(x.y-y.y)>eps;} 33 34 double Cross(node x,node y) 35 { 36 return x.x*y.y-x.y*y.x; 37 } 38 39 double Dot(node x,node y) 40 { 41 return x.x*y.x+x.y*y.y; 42 } 43 44 int dis[Maxn][Maxn]; 45 46 void floyd() 47 { 48 for(int k=1;k<=m;k++) 49 for(int i=1;i<=m;i++) 50 for(int j=1;j<=m;j++) 51 dis[i][j]=mymin(dis[i][j],dis[i][k]+dis[k][j]); 52 } 53 54 int main() 55 { 56 scanf("%d%d",&m,&n); 57 for(int i=1;i<=m+n;i++) 58 { 59 double c; 60 scanf("%lf%lf%lf",&t[i].x,&t[i].y,&c); 61 } 62 memset(dis,63,sizeof(dis)); 63 for(int i=1;i<=m;i++) 64 for(int j=1;j<=m;j++) //if(i!=j&&t[i]!=t[j]) 65 { 66 bool ok=1; 67 for(int k=m+1;k<=n+m;k++) 68 { 69 if(Cross(t[j]-t[i],t[k]-t[i])>eps) {ok=0;break;} 70 if(myabs(Cross(t[j]-t[i],t[k]-t[i]))<=eps&&Dot(t[i]-t[k],t[j]-t[k])>eps) {ok=0;break;} 71 } 72 if(ok) dis[i][j]=1; 73 // if(ok) {dis[i][j]=1;printf("%d->%d\n",i,j);} 74 } 75 floyd(); 76 int ans=INF; 77 for(int i=1;i<=m;i++) ans=mymin(ans,dis[i][i]); 78 if(ans>m) ans=-1; 79 printf("%d\n",ans); 80 return 0; 81 }
2017-02-20 22:09:40
【BZOJ 1027】 (凸包+floyd求最小环)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。