Cod sursa(job #1015744)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 25 octombrie 2013 02:53:32
Problema Adapost Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <fstream>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define N 805
#define oo 0x3f3f3f3f
#define f first
#define s second

using namespace std;

typedef struct{
    double x, y;
} elem;

elem Ad[N], Sold[N];
bool inq[N], viz[N];
int flux, step, n;
double Dist[N], sol, cost;
int C[N][N], S, D, prec[N];
queue<int>Q;
vector<pair<double, pair<int, int> > >distances;
vector<pair<int, double> >G[N];
int nd;

bool cmp(pair<double, pair<int, int> > x, pair<double, pair<int, int> > y)
{
    return x.first < y.first;
}
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(double val)
{
    vector<pair<int, double> >:: iterator it;
    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->f] and Dist[it->f] > Dist[x] + it->s)
            {
                Dist[it->f] = Dist[x] + it->s;
                prec[it->f] = x;
                if(!inq[it->f])
                {
                    inq[it->f] = 1;
                    Q.push(it->f);
                }
            }
    }
    return Dist[D] != oo;
}

bool DF(int x, double val)
{
    vector<pair<int, double> >:: iterator it;
    viz[x] = 1;
    if(x == D) return 1;
    for(it = G[x].begin(); it != G[x].end(); it++)
        if(C[x][it->f] and it->s <= val and !viz[it->f])
        {
            if(DF(it->f, val))
            {
                prec[it->f] = x;
                return 1;
            }
        }
    return 0;
}

bool Search(double val)
{
    memset(viz, 0, sizeof(viz));
    return DF(S, val);
}

bool not_good(double val)
{
    int i;
    while(Search(val))
    {
        for(i = D; i != S; i = prec[i])
            C[prec[i]][i]--, C[i][prec[i]]++;
        flux++;
    }
    return flux < n;
}

int main()
{
    int i, j, x, y;
    //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++) { G[S].push_back(make_pair(i, 0)); G[i].push_back(make_pair(S, 0)); }
    for(j = 1; j <= n; j++) { G[D].push_back(make_pair(j+n, 0)); G[j+n].push_back(make_pair(D, 0)); }

    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            cost = get_dist(Sold[i], Ad[j]);
            distances.push_back(make_pair(cost, make_pair(i, j+n)));
            C[i][j+n] = 1;
            C[S][i] = 1;
            C[j+n][D] = 1;
        }
    nd = distances.size();
    sort(distances.begin(), distances.end(), cmp);
    for(i = 0; i < nd; i++)
    {
        x = distances[i].second.first;
        y = distances[i].second.second;
        G[x].push_back(make_pair(y, distances[i].first));
        G[y].push_back(make_pair(x, -distances[i].first));
        if(!not_good(distances[i].first))
        {
            sol = distances[i].first;
            break;
        }
    }
    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;
        }
    cost = 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;
}