Cod sursa(job #907219)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 7 martie 2013 18:43:43
Problema Adapost Scor 17
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#define N 1000
#define oo 0x3f3f3f3f

using namespace std;

typedef struct{
    double x, y;
} elem;

elem Ad[N], Sold[N];
bool inq[N], viz[N];
int step, cost, Vmax, n, Cost[N][N], Dist[N];
int C[N][N], S, D, prev[N];
queue<int>Q;

int 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);
    int y = (int)((double)x * 10000);
    return y;
}

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(i = 0; i <= D; ++i)
            if(C[x][i] and Dist[i] > Dist[x] + Cost[x][i])
            {
                Dist[i] = Dist[x] + Cost[x][i];
                prev[i] = x;
                if(!inq[i])
                {
                    inq[i] = 1;
                    Q.push(i);
                }
            }
    }
    return Dist[D] != oo;
}

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

bool not_good(int val)
{
    int i, j, sol = 0;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            C[i][j+n] = 1;
            C[j+n][i] = 0;
            C[S][i] = 1;
            C[i][S] = 0;
            C[j+n][D] = 1;
            C[D][j+n] = 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, val;
    double x, y;
    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++)
        for(j = 1; j <= n; j++)
        {
            Cost[i][j+n] = get_dist(Sold[i], Ad[j]);
            Cost[j+n][i] = -Cost[i][j+n];
            C[i][j+n] = 1;
            C[S][i] = 1;
            C[j+n][D] = 1;
            if(Cost[i][j+n] > Vmax) Vmax = Cost[i][j+n];
        }
    for(step = 1; step <= Vmax; step <<= 1);
    for(val = 0; step; step >>= 1)
        if(val+step <= Vmax and not_good(val+step)) val += step;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            C[i][j+n] = 1;
            C[j+n][i] = 0;
            C[S][i] = 1;
            C[i][S] = 0;
            C[i][S] = 0;
            C[j+n][D] = 1;
            C[D][j+n] = 0;
        }
    while(Bellman())
    {
        for(i = D; i != S; i = prev[i])
            C[prev[i]][i]--, C[i][prev[i]]++;
        cost += Dist[D];
    }
    x = (double)val/10000; y = (double)cost/10000;
    fo << setprecision(5) << fixed;
    fo << x << " " << y << "\n";
    return 0;
}