大致题意:
在一个三维空间中有n个点,每个点的坐标都是正整数。第i个点上面有fi个花朵,每个点最多能运送li朵花到其他的点上,每次只能把一个点上的花朵送到距离其R的点上。现在求出最小的R,使得所有的花朵都能被移动到第一个点上。
大致思路:
二分+最大流~~好久没ac的说
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int inf=1<<28; const int nMax=800; const int mMax=100000; class node{ public: int c,u,v,next; };node edge[mMax]; int ne, head[nMax]; int cur[nMax], ps[nMax], dep[nMax]; void addedge(int u, int v,int w){ ////dinic edge[ne].u = u; edge[ne].v = v; edge[ne].c = w; edge[ne].next = head[u]; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c = 0; edge[ne].next = head[v]; head[v] = ne ++; } int dinic(int s, int t){ // dinic int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr =inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++){ edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; } for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){ if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; } if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; } else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res; } //double max(double a,double b){if(a>b)return a;return b;} int sum[nMax][5],num,n; int dis[nMax][nMax]; void getdis(int a,int b){ if(a==b)return; int res; res=(sum[a][0]-sum[b][0])*(sum[a][0]-sum[b][0])+(sum[a][1]-sum[b][1])*(sum[a][1]-sum[b][1])+(sum[a][2]-sum[b][2])*(sum[a][2]-sum[b][2]); dis[a][b]=res; } bool check(int mid){ int i,j,res; ne=2; memset(head,0,sizeof(head)); for(i=1;i<n;i++){ addedge(0,i,sum[i][3]); addedge(i,i+n,sum[i][4]); for(j=1;j<n;j++){ if(dis[i][j]<=mid){ addedge(i+n,j,sum[i][3]); } } if(dis[i][0]<=mid)addedge(i+n,n*2+1,sum[i][4]); } res=dinic(0,2*n+1); if(res>=num)return 1; return 0; } int main(){ int i,j,ans; while(cin>>n){ num=0; for(i=0;i<n;i++){ scanf("%d%d%d%d%d",&sum[i][0],&sum[i][1],&sum[i][2],&sum[i][3],&sum[i][4]); if(i!=0)num+=sum[i][3]; } if(n==1){ printf("%.7lf\n",0); continue; } int left=0,right,mid; for(i=0;i<n;i++){ for(j=0;j<n;j++){ getdis(i,j); right=max(right,dis[i][j]); } } if(!check(right)){ cout<<-1<<endl; continue; } while(right>=left){ mid=(left+right)/2; if(check(mid)){ right=mid-1; ans=mid; } else{ left=mid+1; } } printf("%.7lf\n",sqrt(ans*1.0)); } return 0; }
相关推荐
基于C51单片机Proteu仿真实例及软件源码+文档说明 之-电子琴.zip
均包含代码,文章,部分项目包含ppt
基于java的智乐健身后台管理系统设计与实现.docx
基于java的鲜花销售管理系统设计与实现.docx
内容概要:本文回顾了近年来关于数字孪生(Digital Twin)的概念和技术的发展历程,并详尽介绍了这种技术在未来车间中的潜在应用场景和需克服的难关。数字孪生是一种用于集成物理和虚拟系统的技术手段,它能够在产品设计、智能生产和预防性维护等多个领域发挥作用。 适合人群:研究人员和工程师们希望更好地理解数字孪生的基本理论与具体应用实践。 使用场景及目标:涵盖了从产品的设计、制造过程到服役阶段故障预测的全过程,并探讨了基于DT的具体实施路径。 其他说明:强调了信息物理系统的交互融合是DT成功部署的基础,而建立高准确度的多维虚拟模型、孪生数据驱动和实现动态实时交互将是推进这一前沿概念向前发展的关键。
管理员能够查看、添加、修改和删除景点分类信息,景点分类管理 用户在系统前台可查看系统信息,包括首页、景点信息、酒店信息以及客房信息等 用户要登录界面可输入用户名、密码,点击登录按钮进行登录系统 项目关键技术 开发工具:IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7+ 后端技术:ssm 前端技术:Vue 关键技术:springboot、SSM、vue、MYSQL、MAVEN 数据库工具:Navicat、SQLyog
关键字:UTM/企业防火墙/NGFW 功能:vpn,sdwan,无线控制器,ldap,双因子认证,nat/透明,终端控制,av防病毒,ips入侵检测,应用控制,web过滤, FortiGate UTM/NGFW产品 ①端口:8口、16口、24口、48口 ②层数:二层(接入层交换机、傻瓜式交换机)、三层(核心交换机、汇聚交换机) ③是否网管 网管: 非网管(傻瓜式交换机,即插即用) WEB网管(S1720GW系列) 全网管(S1720GFR系列,S2700以上的型号都为全网管) ④速率:百兆、千兆、万兆等 1.带机量(支持用户数) 2.端口数 3.吞吐量,并发连接数 4.功能 功能差异须知 NG-xxxx产品特有功能 TG-xxxx&NG-xxxx共有功能 TG-xxxx产品特有功能 FW:网络接入、安全防护、高可用性、身份认证、系统服务、系统管理 ●应用层DDOS攻击防护 负载均衡:多链路负载均衡与备份、多链路智能选路技术、多算法的服务器负载均衡 ●异常行为分析:内置统计只能算法,智能学习
简化设计,轻松管理 一键设计:快速创建和管理SQLite3数据库,简化数据库设计流程。 高效查询:强大的查询功能,帮助您轻松处理复杂的SQL语句。 功能全面,灵活便捷 可视化界面:直观的图形界面,让您无需编写繁琐的SQL代码,即可完成数据库设计。 数据同步:支持实时数据同步,确保您的数据库始终保持最新状态。 高度兼容,广泛适用 跨平台支持:适用于Windows、Mac和Linux等多种操作系统,满足不同开发环境的需求。 多语言集成:与C、C++等主流编程语言无缝对接,提高开发效率。 安全可靠,稳定运行 数据备份:内置数据备份与恢复功能,保障数据安全。 性能优化:优化数据库结构,提升查询速度和存储效率。
小程序-滴滴作业.zip 小程序-滴滴作业.zip 小程序-滴滴作业.zip
地线贴标_复制.ezd
Chrome主题-开阔绿地草地主题
基于java校园兼职平台设计与实现.docx
基于java的旅游管理系统设计与实现.docx
基于java的技术大健康综合咨询问诊平台的设计与实现.docx
均包含代码,文章,部分项目包含ppt
项目工程资源经过严格测试可直接运行成功且功能正常的情况才上传,可轻松复刻,拿到资料包后可轻松复现出一样的项目,本人系统开发经验充足(全领域),有任何使用问题欢迎随时与我联系,我会及时为您解惑,提供帮助。 【资源内容】:包含完整源码+工程文件+说明(如有)等。答辩评审平均分达到96分,放心下载使用!可轻松复现,设计报告也可借鉴此项目,该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的。 【提供帮助】:有任何使用问题欢迎随时与我联系,我会及时解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 下载后请首先打开README文件(如有),项目工程可直接复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用。
基于java的共享客栈管理系统设计与实现.docx
基于java的车库智能管理平台设计与实现.docx
基于java的学生宿舍管理设计与实现.docx
【C++】项目设计资源 【C++】新手入门教程 包含例子和相关说明