FlowerTime Limit:8 Seconds Memory Limit:65536 KB Special Judge
Gaoand his girlfriend’s relationship becomes better and better after they flying balloon last week. Thus,Gaowants to play a simple but evil game with his girlfriend at a late night.
The game is simple: there is a three-dimensional space,GaochoosesNpoints to put flowers. For the pointi, it hasFiflowers. And his girlfriend has to move all these flowers topoint 1altogether. As everyone knows, his girlfriend is not strong likeGao, so she can move flowers from one point to another if and only if the Euclidean distance between two points are smaller or equal toR. In another words, she perhaps has to move flowers to the intermediate point for finally moving all flowers to the point one. In order to stay with his girlfriend as much time as possible, he asks his girlfriend, for the pointi, that she can only move out no more thanLiflowers (including the points as an intermediate point).
Can you help his poor girlfriend to calculate the minimalR?
Input
There are multiple cases.
For each case, the first line contains an integerN(1 ≤N≤ 100), which means there areNpoints.
For the nextNlines, each line contains five integers,Xi,Yi,Zi,FiandLi.Xi,YiandZiare the coordinate of pointi(0 ≤Xi, Yi, Zi≤ 20000),Fimeans there areFiflowers at the beginning.Limeans this point can be moved out no more thanLiflowers.
Output
For each test case, it contains one real number indicating the minimalR. The results should be rounded to seven decimal places. If there is no solution for this case, please output -1. Output’s absolute error less than 1e-6 will be accepted.
Sample Input21 1 1 1 12 2 2 2 2Sample Output1.7320508
题意：三维空间中有n个点，序号为1-n，每个点有一个坐标，每个点上有F[i]朵花，，每个点只允许L[i]朵花从这个点转移出到
但要符合L[i]的限制，但是Gao的女朋友一次能走的距离是R，如果Gao的女朋友把i号点花转移到j号点上，Gao的女朋友需要
行走的距离是dis(i,j)，现在问：Gao的女朋友要完成这项任务需要的最小R，如果完成不了输出-1。
题解：二分答案，建图跑最大流，判断是否满流。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define ll long longusing namespace std;const int MAXN = 410;//点数的最大值const int MAXM = 80010;//边数的最大值const int INF = 0x3f3f3f3f;struct Edge {int to,next,cap,flow;} edge[MAXM]; int tol,n,m,sum;int head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];struct Point {double x,y,z;int f,l;} a[MAXN];double d[MAXN][MAXN];void init() {tol = 0;memset(head,-1,sizeof(head));}double dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));}void addedge(int u,int v,int w,int rw = 0) {edge[tol].to = v;edge[tol].cap = w;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = rw;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++;}int Q[MAXN];void BFS(int start,int end) {memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0] = 1;int front = 0, rear = 0;dep[end] = 0;Q[rear++] = end;while(front != rear) {int u = Q[front++];for(int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].to;if(dep[v] != -1)continue;Q[rear++] = v;dep[v] = dep[u] + 1;gap[dep[v]]++;}}}int S[MAXN];int sap(int start,int end,int N) {BFS(start,end);memcpy(cur,head,sizeof(head));int top = 0;int u = start;int ans = 0;while(dep[start] < N) {if(u == end) {int Min = INF;int inser;for(int i = 0; i < top; i++)if(Min > edge[S[i]].cap – edge[S[i]].flow) {Min = edge[S[i]].cap – edge[S[i]].flow;inser = i;}for(int i = 0; i < top; i++) {edge[S[i]].flow += Min;edge[S[i]^1].flow -= Min;}ans += Min;top = inser;u = edge[S[top]^1].to;continue;}bool flag = false;int v;for(int i = cur[u]; i != -1; i = edge[i].next) {v = edge[i].to;if(edge[i].cap – edge[i].flow && dep[v]+1 == dep[u]) {flag = true;cur[u] = i;break;}}if(flag) {S[top++] = cur[u];u = v;continue;}int Min = N;for(int i = head[u]; i != -1; i = edge[i].next)if(edge[i].cap – edge[i].flow && dep[edge[i].to] < Min) {Min = dep[edge[i].to];cur[u] = i;}gap[dep[u]]–;if(!gap[dep[u]])return ans;dep[u] = Min + 1;gap[dep[u]]++;if(u != start)u = edge[S[–top]^1].to;}return ans;}bool slove(double R) {init();int s=0,t=1;for(int i=2; i<=n; i++) {addedge(i,i+n,a[i].l);addedge(s,i,a[i].f);}for(int i=2; i<=n; i++) {for(int j=i+1; j<=n; j++) {if(d[i][j]<=R) {addedge(i+n,j,INF);addedge(j+n,i,INF);}}if(d[i][1]<=R)addedge(i+n,1,INF);}return sum==sap(s,t,2*n);}int main() {//freopen("test.in","r",stdin);while(cin>>n) {sum=0;for(int i=1; i<=n; i++) {scanf("%lf%lf%lf%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].f,&a[i].l);sum+=a[i].f;}sum-=a[1].f;double MaxD=0;for(int i=1; i<=n; i++) {for(int j=i+1; j<=n; j++) {d[i][j]=d[j][i]=dis(a[i],a[j]);MaxD=max(MaxD,d[i][j]);}}int flag=0;double l=0.0,r=MaxD;for(int i=0; i<100; i++) {double mid=(l+r)/2;if(slove(mid)) {r=mid;flag=1;} else l=mid;}if(flag)printf("%.7f\n",l);elseprintf("-1\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
如果有可能，我带你去远行。
