大致题意:
在一个三维空间中有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; }
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]
Problem Arrangement zoj 3777
ZOJ题目答案源码
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
浙大ACM网上的题目分类,以及部分题目的题解,包括题目,对于没联网的很适用,即使就有网的也很用的,里面有些题解很祥细……
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。