fork download 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int x[100],y[100],z[100],n,all;
  9. int f[100],l[100],d[100][100];
  10.  
  11. class Dinic{
  12. public:
  13.     static const int INF = 1000000007, SIZE = 205;
  14.     int c[SIZE][SIZE];
  15.     int n,s,t,l[SIZE],e[SIZE];
  16.     int flow(int maxf = INF){
  17.         int left=maxf;
  18.         while(build()) left-=push(s,left);
  19.         return maxf-left;
  20.     }
  21.     int push(int x, int f){
  22.         if(x==t) return f;
  23.         int& y=e[x],sum=f;
  24.         for(;y<n;y++) if(c[x][y]>0 && l[x]+1==l[y]){
  25.             int cnt=push(y,min(sum,c[x][y]));
  26.             c[x][y]-=cnt;
  27.             c[y][x]+=cnt;
  28.             sum-=cnt;
  29.             if(!sum) return f;
  30.         }
  31.         return f-sum;
  32.     }
  33.     bool build(){
  34.         int m=0;
  35.         memset(l,255,sizeof(l));
  36.         l[e[m++]=s]=0;
  37.         for(int i=0;i<m;i++) for(int y=0;y<n;y++)
  38.             if(c[e[i]][y]>0 && l[y]<0) l[e[m++]=y]=l[e[i]]+1;
  39.         memset(e,0,sizeof(e));
  40.         return l[t]>=0;
  41.     }
  42. }net;
  43.  
  44. bool gao(int r, int tmp){
  45.     memset(net.c,0,sizeof(net.c));
  46.     for(int i=0;i<n;i++){
  47.         net.c[n+n][i]=f[i];
  48.         net.c[i][i+n]=l[i];
  49.         for(int j=0;j<n;j++)
  50.             if(d[i][j]<=r) net.c[i+n][j]=Dinic::INF;
  51.     }
  52.     net.n=n+n+1;
  53.     net.s=n+n;
  54.     net.t=0;
  55.     return net.flow()!=all;
  56. }
  57.  
  58. int main(){
  59.     while(scanf("%d",&n)==1){
  60.         vector<int> u;
  61.         all=0;
  62.         for(int i=0;i<n;i++){
  63.             scanf("%d%d%d%d%d",x+i,y+i,z+i,f+i,l+i);
  64.             all+=f[i];
  65.             for(int j=0;j<i;j++){
  66.                 int dx=x[i]-x[j];
  67.                 int dy=y[i]-y[j];
  68.                 int dz=z[i]-z[j];
  69.                 u.push_back(d[i][j]=d[j][i]=dx*dx+dy*dy+dz*dz);
  70.             }
  71.         }
  72.         sort(u.begin(),u.end());
  73.         u.erase(unique(u.begin(),u.end()),u.end());
  74.         size_t i=lower_bound(u.begin(),u.end(),0,gao)-u.begin();
  75.         if(i==u.size()) puts("-1"); else
  76.                         printf("%.7f\n",sqrt(u[i]));
  77.     }
  78. }
  79.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ITHM2U
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!