Cod sursa(job #1015727)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 25 octombrie 2013 01:10:36
Problema Adapost Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#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, n;
double Cost[N][N], Dist[N], sol, cost;
int C[N][N], S, D, prec[N];
queue<int>Q;
vector<double>distances;
int nd;

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

bool BF(double 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;
            prec[i] = x;
            Q.push(i);
        }
    }
    return viz[D];
}

bool not_good(double 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(BF(val))
    {
        for(i = D; i != S; i = prec[i])
            C[prec[i]][i]--, C[i][prec[i]]++;
        sol++;
    }
    return sol < n;
}

int main()
{
    int i, j;
    //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];
            distances.push_back(Cost[i][j+n]);
            C[i][j+n] = 1;
            C[S][i] = 1;
            C[j+n][D] = 1;
        }
    sort(distances.begin(), distances.end());
    nd = distances.size();
    for(step = 1; step <= nd; step <<= 1);
    for(i = 0; step; step >>= 1)
        if(i+step < nd and not_good(distances[i+step])) i += step;
    if(not_good(distances[i])) i++; //Might work
    sol = distances[i];
    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(sol))
//    {
//        for(i = D; i != S; i = prec[i])
//            C[prec[i]][i]--, C[i][prec[i]]++;
//        cost += Dist[D];
//    }
    fo << setprecision(5) << fixed;
    fo << sol << " " << cost << "\n";
    return 0;
}