Cod sursa(job #422648)

Utilizator vladiiIonescu Vlad vladii Data 22 martie 2010 22:59:18
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
#define INF 999999999
vector<int> G[401];
vector<pair<int, double> > V[805];
int TT[805], C[805][805], F[805][805]; 
int N, L[401], R[401], U[401];
double D[401][401], sol, dist;
double val[401*401], Di[805];;
struct Coord {
    double x, y;
} S[401], A[401];

int pairUp(int nod) {
    if(U[nod]) return 0;
    U[nod]=1;
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(!R[(*it)]) {
              L[nod]=(*it);
              R[(*it)]=nod;
              return 1;
         }
    }
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(pairUp(R[(*it)])) {
              L[nod]=(*it);
              R[(*it)]=nod;
              return 1;
         }
    }
    return 0;
}

int Verifica(double d) {
    int i, j;
    for(i=1; i<=N; i++) {
         G[i].clear(); R[i]=L[i]=0;
    }
    for(i=1; i<=N; i++) {
         for(j=1; j<=N; j++) {
              if(D[i][j]<=d) { G[i].push_back(j); }
         }
    }
    int ok=1;
    while(ok) {
         memset(U, 0, sizeof(U));
         ok=0;
         for(i=1; i<=N; i++) {
              if(!L[i]) {
                   if(pairUp(i)) { ok=1; }
              }
         }
    }
    for(i=1; i<=N; i++) {
         if(!L[i]) { return 0; }
    }
    return 1;
}

struct cmp 
{ 
bool operator()(const int &a, const int &b) 
{ 
return Di[a]>Di[b];
} 
};

double BellmanFord() {
    int i, j, p, q;
    priority_queue <int, vector <int>, cmp > Q;
    bool InQueue[805];
    for(i=0; i<=2*N+2; i++) {
         Di[i]=INF; InQueue[i]=0;
         TT[i]=-1;
    }
    Di[1]=0; InQueue[1]=1;
    Q.push(1);
    while(!Q.empty()) {
         p=Q.top(); Q.pop(); InQueue[p]=0;
         for(vector<pair<int, double> >::iterator it=V[p].begin(); it!=V[p].end(); it++) {
              if(C[p][(*it).first]>F[p][(*it).first] && Di[p]+(*it).second<Di[(*it).first]) {
                   Di[(*it).first]=Di[p]+(*it).second;
                   TT[(*it).first]=p;
                   if(!InQueue[(*it).first]) {
                        InQueue[(*it).first]=1;
                        Q.push((*it).first);
                   }
              }
         }
    }
    if(Di[2*N+2]<INF) {
         int fmin=INF;
         for(i=2*N+2; i!=1; i=TT[i]) {
              fmin=min(fmin, C[TT[i]][i]-F[TT[i]][i]);
         }
         for(i=2*N+2; i!=1; i=TT[i]) {
              F[TT[i]][i]+=fmin;
              F[i][TT[i]]-=fmin;
         }
         return Di[2*N+2]*fmin;
    }
    return 0;
}

int main() {
    fstream f1, f2;
    int i, j, p, q, nr=0;
    f1.open("adapost.in", ios::in);
    f1>>N;
    for(i=1; i<=N; i++) {
         f1>>S[i].x>>S[i].y;
    }
    for(i=1; i<=N; i++) {
         f1>>A[i].x>>A[i].y;
    }
    for(i=1; i<=N; i++) {
         for(j=1; j<=N; j++) {
              //distana de la soldatul i la adapostul j
              D[i][j]=(double)(A[j].x-S[i].x)*(A[j].x-S[i].x)+(double)(A[j].y-S[i].y)*(A[j].y-S[i].y);
              D[i][j]=sqrt(D[i][j]);
              val[nr]=D[i][j]; nr++;
         }
    }
    sort(val, val+nr);
    int ls=0, ld=nr-1;
    while(ls<=ld) {
         int mij=(ls+ld)>>1;
         double LDS=(double)val[mij];
         if(Verifica(LDS)) {
              sol=LDS;
              ld=mij-1;
         }
         else {
              ls=mij+1;
         }
    }
    //construiesc graful pentru flux maxim de cost minim
    for(i=1; i<=N; i++) {
         for(j=1; j<=N; j++) {
              if(D[i][j]<=sol) {
                   double asd=D[i][j];
                   V[i+1].push_back(make_pair(N+1+j, asd));
                   V[N+1+j].push_back(make_pair(i+1, -asd));
                   C[i+1][N+1+j]=1;
              }
         }
    }
    for(i=2; i<=N+1; i++) {
         V[1].push_back(make_pair(i, 0));
         V[i].push_back(make_pair(1, 0));
         C[1][i]=1;
    }
    for(i=N+2; i<=2*N+1; i++) {
         V[i].push_back(make_pair(2*N+2, 0));
         V[2*N+2].push_back(make_pair(i, 0));
         C[i][2*N+2]=1;
    }
    //fac flux maxim de cost minim de la sursa 1 la destinatia 2*N+2
    double flow=0, f=1;
    while(f) {
         f=BellmanFord();
         flow+=f;
    }
    f2.open("adapost.out", ios::out);
    f2<<sol<<" "<<(double)flow<<endl;
    f1.close(); f2.close();
    return 0;
}