Cod sursa(job #1015736)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 25 octombrie 2013 01:44:30
Problema Adapost Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <fstream>
#include <utility>
#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 flux, step, n;
double Cost[N][N], Dist[N], sol, cost;
int C[N][N], S, D, prec[N];
queue<int>Q;
vector<pair<double, pair<int, int> > >distances;
vector<int>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<int> :: 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] and Dist[*it] > Dist[x] + Cost[x][*it] and Cost[x][*it] <= val)
            {
                Dist[*it] = Dist[x] + Cost[x][*it];
                prec[*it] = x;
                if(!inq[*it])
                {
                    inq[*it] = 1;
                    Q.push(*it);
                }
            }
    }
    return Dist[D] != oo;
}

bool BF(double val)
{
    vector<int> :: iterator it;
    int x, i;
    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 Cost[x][*it] <= val and !viz[*it])
        {
            viz[*it] = 1;
            prec[*it] = x;
            Q.push(*it);
        }
    }
    return viz[D];
}

bool not_good(double val)
{
    int i;
    while(BF(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(i); G[i].push_back(S); }
    for(j = 1; j <= n; j++) { G[D].push_back(j+n); G[j+n].push_back(D); }

    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(make_pair(Cost[i][j+n], 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(y); G[y].push_back(x);
        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;
        }
//    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;
}