Cod sursa(job #978187)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 28 iulie 2013 08:04:51
Problema Adapost Scor 21
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>

#define ff first
#define ss second
#define newn a[x][i]

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

const int N = 410;
const int M = 820;
const int s = 0;
const int oo = 3000;

typedef pair <double, double> nod;
typedef pair <double, int> heap;
vector <nod> sold;
vector <short> a[M];
vector <bool> uz(M);
int n, d, f[M][M], c[M][M], t[M];
double cst[M][M], dist[M], cmin, maxc;
priority_queue < heap, vector<heap>, greater<heap> > h;

void Read()
{
    fin>>n;
    d = n + n + 2;
    for(int i=1; i<=n; i++)
    {
        double x, y;
        fin>>x>>y;
        c[s][i] = 1;
        a[s].push_back(i);
        sold.push_back(nod(x, y));
    }
    for(int i=1; i<=n; i++)
    {
        double x, y; int vf = i + n;
        fin>>x>>y;
        c[vf][d] = 1;
        a[vf].push_back(d);
        for(int j=0; j<n; j++)
        {
            c[j+1][vf] = 1;
            a[j+1].push_back(vf);
            a[vf].push_back(j+1);
            double difx = x - sold[j].ff, dify = y - sold[j].ss;
            double cost = sqrt(difx*difx + dify*dify);
            if(maxc < cost) maxc = cost;
            cst[j+1][vf] = cost;
            cst[vf][j+1] = -cost;
        }
    }
}

inline bool Dijkstra(const double val)
{
    int m = 2*n+3;
    for(int i=0; i<=m; i++) dist[i] = oo;
    h.push(heap(0, s));  dist[s] = 0;
    while(!h.empty())
    {
        int x = h.top().second; double dd = h.top().first; h.pop();
        if(dist[x] != dd) continue;
        for(unsigned i=0; i<a[x].size(); i++)
             if(f[x][newn] < c[x][newn] && val >= cst[x][newn])
             {
                if(dist[x] + cst[x][newn] < dist[newn])
                {
                    t[newn] = x;
                    dist[newn] = dist[x] + cst[x][newn];
                    h.push(heap(dist[newn], newn));
                }
             }
    }
    return (dist[d] != oo);
}

inline bool OK(const double val)
{
    int flux = 0, m = n + n +2; cmin = 0;
    for(int i=0; i<=m; i++)
        for(int j=0; j<=m; j++)
            f[i][j] = 0;
    while(Dijkstra(val))
    {
        for(int j=d; j!=s; j=t[j])
            f[t[j]][j]++, f[j][t[j]]--;
        flux++;
        cmin += dist[d];
    }
    return (flux == n);
}

int main()
{
    Read();
    double st = 0, dr = 2000, mid;
    while(dr - st > 0.001)
    {
        mid = (dr+st) / 2;
        if(OK(mid)) dr = mid;
        else st = mid;
    }
    fout<<fixed<<setprecision(5)<<dr<<' '<<cmin;
    return 0;
}