Cod sursa(job #2081325)

Utilizator LucianTLucian Trepteanu LucianT Data 4 decembrie 2017 16:56:24
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.57 kb
#include <bits/stdc++.h>
using namespace std;
const int maxN=405;
const int INF=0x3f3f3f3f;
const double EPS=1e-7;

bool vis[maxN];
int _left[maxN],_right[maxN];

double dist[2*maxN];
int t[2*maxN];
vector<int> v[2*maxN];

int flow[2*maxN][2*maxN];
double cost[2*maxN][2*maxN];
bool cap[2*maxN][2*maxN];

double sol;
int n,source,sink;
pair<double,double> man[maxN],house[maxN];
vector<double> distances;

bool pairup(int nod,double maxEdge)
{
    if(vis[nod])
        return false;
    vis[nod]=true;

    for(int i=1;i<=n;i++)
        if(cost[nod][n+i]<=maxEdge && !_right[i]){
            _right[i]=nod;
            _left[nod]=i;
            return true;
        }

    for(int i=1;i<=n;i++)
        if(cost[nod][n+i]<=maxEdge && pairup(_right[i],maxEdge)){
            _right[i]=nod;
            _left[nod]=i;
            return true;
        }

    return false;
}

bool perfectMatch(double maxEdge)
{
    memset(_left,0,sizeof(_left));
    memset(_right,0,sizeof(_right));

    bool ok=true;
    while(ok)
    {
        ok=false;
        memset(vis,false,sizeof(vis));

        for(int i=1;i<=n;i++)
            if(!_left[i] && pairup(i,maxEdge))
                ok=true;
    }

    for(int i=1;i<=n;i++)
        if(!_left[i])
            return false;

    return true;
}

bool bellmanford()
{
    memset(t,0,sizeof(t));
    bitset<2*maxN> inQue;
    queue<int> Que;

    for(int i=1;i<=2*n+1;i++)
        dist[i]=INF;

    dist[source]=0;
    Que.push(source);
    inQue[source]=true;

    while(!Que.empty())
    {
        int nod=Que.front();
        Que.pop();
        inQue[nod]=false;

        for(auto it:v[nod])
            if(flow[nod][it]<cap[nod][it] && cost[nod][it]<=sol && dist[it]>dist[nod]+cost[nod][it]){
                dist[it]=dist[nod]+cost[nod][it];
                t[it]=nod;

                if(!inQue[it]){
                    Que.push(it);
                    inQue[it]=true;
                }
            }
    }

    return dist[sink]<INF;
}

int main()
{
    ifstream f("adapost.in");
    ofstream g("adapost.out");

    f>>n;
    sink=2*n+1;
    for(int i=1;i<=n;i++)
        f>>man[i].first>>man[i].second;

    for(int i=1;i<=n;i++)
        f>>house[i].first>>house[i].second;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            double x=man[i].first-house[j].first;
            double y=man[i].second-house[j].second;

            double edge=sqrt(x*x+y*y);
            cost[i][j+n]=edge;
            cost[j+n][i]=-edge;

            distances.push_back(edge);
        }

    sort(distances.begin(),distances.end());

    int st=0,dr=n*n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;

        if(perfectMatch(distances[mij])){
            sol=distances[mij];
            dr=mij-1;
        }
        else st=mij+1;
    }

    for(int i=1;i<=n;i++){
        cap[source][i]=1;
        v[source].push_back(i);
        v[i].push_back(source);

        cap[i+n][sink]=1;
        v[i+n].push_back(sink);
        v[sink].push_back(i+n);
    }

    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(cost[i][j]<=sol){
                v[i].push_back(j);
                v[j].push_back(i);
                cap[i][j]=1;
            }

    double mincost=0;
    while(bellmanford()){
        for(int nod=sink;nod!=source;nod=t[nod]){
            flow[t[nod]][nod]++;
            flow[nod][t[nod]]--;
        }
        mincost+=dist[sink];
    }

    g<<setprecision(5)<<fixed<<sol<<" "<<mincost;

    return 0;
}