Cod sursa(job #1891418)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 23 februarie 2017 23:45:03
Problema Adapost Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <bits/stdc++.h>
#define MAXN 1000
#define MAXQ (1<<17)
#define INF 1000000000
#define x first
#define y second
std::pair <double,double> A[MAXN+1];
std::pair <double,double> B[MAXN+1];
double v[MAXN*MAXN+1];
inline double Dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
std::vector <int> G[MAXN+1];
double cost[MAXN+1][MAXN+1];
int flow[MAXN+1][MAXN+1];
int cap[MAXN+1][MAXN+1];
int from[MAXN+1];
int Q[MAXQ];
double best[MAXN+1];
bool inQ[MAXN+1];
bool viz[MAXN+1];
int n;
inline void add(int &x){
   x++;
   x&=(MAXQ-1);
}
inline bool BellmanFord(int s,int d,double dist){
    int b=0,e=1;
    memset(viz,0,sizeof(viz));
    best[0]=0;
    for(int i=1;i<=2*n+1;i++)
      best[i]=INF;
    Q[0]=s;
    viz[s]=1;
    inQ[s]=1;
    while(b!=e){
       int nod=Q[b];
       inQ[nod]=0;
       add(b);
       for(int i=0;i<G[nod].size();i++){
          int x=G[nod][i];
          if(cap[nod][x]>flow[nod][x]&&cost[nod][x]<=dist&&best[x]>best[nod]+cost[nod][x]){
              best[x]=best[nod]+cost[nod][x];
              from[x]=nod;
              if(!inQ[x]){
                inQ[x]=1;
                Q[e]=x;
                viz[x]=1;
                add(e);
              }
          }
       }
    }
    return viz[d];
}
double ans;
inline int MaxFlow(double dist){
    int flux=0;
    ans=0;
    memset(flow,0,sizeof(flow));
    while(BellmanFord(0,2*n+1,dist)){
        int min=INF;
        int nod=2*n+1;
        while(nod!=0){
           if(min>cap[from[nod]][nod]-flow[from[nod]][nod])
             min=cap[from[nod]][nod]-flow[from[nod]][nod];
           nod=from[nod];
        }
        nod=2*n+1;
        while(nod!=0){
           flow[from[nod]][nod]+=min;
           flow[nod][from[nod]]-=min;
           ans+=1.0*min*cost[from[nod]][nod];
           nod=from[nod];
        }
        flux+=min;
    }
    return flux;
}
int pair[MAXN+1];
inline bool Find(int nod,double dist){
   viz[nod]=1;
   for(int i=0;i<G[nod].size();i++){
     int x=G[nod][i];
     if(cost[nod][x]<=dist&&viz[x]==0&&pair[x]==0){
        pair[nod]=x;
        pair[x]=nod;
        return 1;
     }
   }
   for(int i=0;i<G[nod].size();i++){
      int x=G[nod][i];
      if(!viz[pair[x]]&&cost[nod][x]<=dist&&Find(pair[x],dist)==1){
         pair[nod]=x;
         pair[x]=nod;
         return 1;
      }
   }
   return 0;
}
inline int Calc(double dist){
   bool flag=1;
   memset(pair,0,sizeof(pair));
   while(flag){
      flag=0;
      memset(viz,0,sizeof(viz));
      for(int i=1;i<=n;i++)
       if(pair[i]==0)
          flag|=Find(i,dist);
   }
   int cnt=0;
   for(int i=1;i<=n;i++)
     if(pair[i])
       cnt++;
   return cnt;
}
int main(){
    FILE*fi,*fout;
    int i,j;
    fi=fopen("adapost.in" ,"r");
    fout=fopen("adapost.out" ,"w");
    fscanf(fi,"%d " ,&n);
    for(i=1;i<=n;i++)
       fscanf(fi,"%lf %lf " ,&A[i].x,&A[i].y);
    for(i=1;i<=n;i++)
       fscanf(fi,"%lf %lf " ,&B[i].x,&B[i].y);
    int m=0;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++){
        cost[i][j+n]=Dist(A[i].x,A[i].y,B[j].x,B[j].y);
        cost[j+n][i]=-cost[i][j+n];
        cap[i][j+n]=1;
        cap[j+n][i]=0;
        G[i].push_back(j+n);
        G[j+n].push_back(i);
        v[++m]=cost[i][j+n];
     }
    for(i=1;i<=n;i++){
      G[0].push_back(i);
      G[i].push_back(0);
      cap[0][i]=1;
      cost[0][i]=0;
    }
    for(i=n+1;i<=2*n;i++){
      G[i].push_back(2*n+1);
      G[2*n+1].push_back(i);
      cap[i][2*n+1]=1;
      cost[i][2*n+1]=0;
    }
    std::sort(v+1,v+m+1);
    int cnt=Calc(v[m]);
    int rez=0;
    for(int pas=1<<14;pas;pas>>=1)
     if(rez+pas<=m&&Calc(v[rez+pas])<cnt)
       rez+=pas;
    for(i=1;i<=n;i++)
      G[i].clear();
    for(i=1;i<=n;i++)
     for(j=n+1;j<=2*n;j++)
      if(cost[i][j]<=v[rez+1]){
        G[i].push_back(j);
        G[j].push_back(i);
      }
    MaxFlow(v[rez+1]);
    fprintf(fout,"%lf %lf" ,v[rez+1],ans);
    fclose(fi);
    fclose(fout);
    return 0;
}