Cod sursa(job #907341)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 7 martie 2013 21:07:04
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <fstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define N 1000
#define pb push_back
#define eps 0.001
#define oo 0x3f3f3f3f

using namespace std;

typedef struct{
    double x, y;
} elem;

vector<int> :: iterator it;
vector<int> G[N];
elem Ad[N], Sold[N];
bool inq[N], viz[N];
double l, m, r, cost, Vmax, Cost[N][N], Dist[N];
int C[N][N], S, D, n, prev[N];
queue<int>Q;

double get_dist(elem a, elem b)
{
    double x = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    x = sqrt((double)x);
    return x;
}

bool Bellman()
{
    int i, x;
    for(i = S; i <= D; i++) Dist[i] = oo;
    Dist[S] = 0;
    Q.push(S);
    while(!Q.empty())
    {
        x = Q.front(); Q.pop();
        inq[x] = 0;
        for(it = G[x].begin(); it != G[x].end(); ++it)
            if(C[x][*it] and Dist[*it] > eps + Dist[x] + Cost[x][*it])
            {
                Dist[*it] = Dist[x] + Cost[x][*it];
                prev[*it] = x;
                if(!inq[*it])
                {
                    inq[*it] = 1;
                    Q.push(*it);
                }
            }
    }
    return Dist[D] != oo;
}

bool DF(double val)
{
    int x;
    memset(viz, 0, sizeof(viz));
    Q.push(S);
    viz[S] = 1;
    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        for(it = G[x].begin(); it != G[x].end(); ++it)
        if(C[x][*it] and val > Cost[x][*it] and !viz[*it])
        {
            viz[*it] = 1;
            prev[*it] = x;
            Q.push(*it);
        }
    }
    return viz[D];
}

bool not_good(double val)
{
    int i, sol = 0;
    while(DF(val))
    {
        for(i = D; i != S; i = prev[i])
            C[prev[i]][i]--, C[i][prev[i]]++;
        sol++;
    }
    return sol != n;
}

int main()
{
    int i, j;
    double val;
    ifstream fi("adapost.in");
    ofstream fo("adapost.out");
    fi >> n;
    S = 0; D = 2*n+1;
    for(i = 1; i <= n; i++)
    {
        fi >> Sold[i].x >> Sold[i].y;
    }
    for(i = 1; i <= n; i++)
    {
        fi >> Ad[i].x >> Ad[i].y;
    }
    for(i = 1; i <= n; i++)
    {
        G[S].pb(i); G[i].pb(S);
        G[i+n].pb(D); G[D].pb(i+n);
        C[S][i] = 1;
        C[i+n][D] = 1;
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            G[i].pb(j+n);
            G[j+n].pb(i);
            Cost[i][j+n] = get_dist(Sold[i], Ad[j]);
            Cost[j+n][i] = -Cost[i][j+n];
            C[i][j+n] = 1;
            if(Cost[i][j+n] > Vmax) Vmax = Cost[i][j+n];
        }
    l = 0; r = Vmax;
    while(r - l > eps)
    {
        m = (l+r)/2;
        if(not_good(m)) l = m; else r = m;
    }
    val = l;
    //am stabilit deja Vmax
    for(i = 0; i <= D; i++) G[i].clear();
    for(i = 1; i <= n; i++)
    {
        G[S].pb(i); G[i].pb(S);
        G[i+n].pb(D); G[D].pb(i+n);
        C[S][i] = 1; C[i][S] = 0;
        C[i+n][D] = 1; C[D][i+n] = 0;
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            C[i][j+n] = C[j+n][i] = 0;
            if(Cost[i][j+n] < val + eps)
            {
                C[i][j+n] = 1;
                G[i].pb(j+n);
                G[j+n].pb(i);
            }
        }
    while(Bellman())
    {
        for(i = D; i != S; i = prev[i])
            C[prev[i]][i]--, C[i][prev[i]]++;
        cost += Dist[D];
    }
    fo << setprecision(5) << fixed;
    fo << val << " " << cost << "\n";
    return 0;
}