Cod sursa(job #1891431)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 24 februarie 2017 00:09:47
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <bits/stdc++.h>
#define MAXN 810
#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];
int n;
inline bool BellmanFord(double dist){
    int b=0,e=1;
    best[0]=0;
    for(int i=1;i<=2*n+1;i++)
      best[i]=INF;
    Q[0]=0;
    inQ[0]=1;
    while(b<e){
       int nod=Q[b];
       int l=G[nod].size();
       inQ[nod]=0;
       b++;
       for(int i=0;i<l;i++){
          int x=G[nod][i];
          if(cap[nod][x]>flow[nod][x]&&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;
                e++;
              }
          }
       }
    }
    return best[2*n+1]<INF;
}
double ans;
inline int MaxFlow(double dist){
    int flux=0;
    ans=0;
    while(BellmanFord(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;
           nod=from[nod];
        }
        ans+=1.0*min*best[2*n+1];
        flux+=min;
    }
    return flux;
}
int pair[MAXN+1];
bool viz[MAXN+1];
inline bool Find(int nod,double dist){
   viz[nod]=1;
   for(int x=n+1;x<=2*n;x++)
     if(cost[nod][x]<=dist&&viz[x]==0&&pair[x]==0){
        pair[nod]=x;
        pair[x]=nod;
        return 1;
     }
   for(int x=n+1;x<=2*n;x++)
      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;
        v[++m]=cost[i][j+n];
     }
    std::sort(v+1,v+m+1);
    int rez=0;
    for(int pas=1<<14;pas;pas>>=1)
     if(rez+pas<=m&&Calc(v[rez+pas])<n)
       rez+=pas;
    for(i=1;i<=n;i++){
      G[0].push_back(i);
      G[i].push_back(0);
      cap[0][i]=1;
    }
    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;
    }
    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;
}