Cod sursa(job #1035781)

Utilizator dariusdariusMarian Darius dariusdarius Data 18 noiembrie 2013 20:04:27
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
vector<int> G[805];
double cost[805][805];
int C[805][805],F[805][805];
int p[805];double d[805];
struct Point {double x,y;} a[405],b[405];
inline bool cmp(int a,int b) {return d[a]>d[b];}
int Q[1000005];
int U[805];
bool BellmanFord()
{
    for(int i=1;i<=2*n+1;i++)
    {
        d[i]=1000000000.0;
        p[i]=-1;
    }
    int L=1;
    d[0]=0;Q[L]=0;
    memset(U,0,sizeof(U));
    U[0]=1;
    for(int i=1;i<=L;U[Q[i++]]=0)
        for(vector<int>::iterator it=G[Q[i]].begin();it!=G[Q[i]].end();it++)
            if(C[Q[i]][*it]-F[Q[i]][*it]>0 && d[Q[i]]+cost[Q[i]][*it]<d[*it])
            {
                d[*it]=d[Q[i]]+cost[Q[i]][*it];
                p[*it]=Q[i];
                if(!U[*it])
                {
                    Q[++L]=*it;
                    U[Q[L]]=1;
                }
            }
    if(d[2*n+1]<999999999.0)
        return true;
    return false;
}
double MaxFlowMinCost(double lim)
{
    memset(F,0,sizeof(F));
    for(int i=1;i<=2*n;i++)
        G[i].clear();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(cost[i][j+n]<=lim)
            {
                G[i].push_back(n+j);
                G[n+j].push_back(i);
            }
    int total=0;double tc=0;
    while(BellmanFord())
    {
        int u=2*n+1,flux=1000000000;
        while(u!=0)
        {
            flux=min(flux,C[p[u]][u]-F[p[u]][u]);
            u=p[u];
        }
        u=2*n+1;
        while(u!=0)
        {
            F[p[u]][u]+=flux;
            F[u][p[u]]-=flux;
            u=p[u];
        }
        total+=flux;
        tc+=d[2*n+1]*flux;
    }
    if(total!=n)
        return -1.0;
    return tc;
}
int main()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        G[0].push_back(i);
        G[i].push_back(0);
        G[n+i].push_back(2*n+1);
        G[2*n+1].push_back(n+i);
    }
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&b[i].x,&b[i].y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cost[i][j+n]=sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y));
            cost[j+n][i]=-cost[i][j+n];
            C[i][j+n]=1;
        }
    for(int i=1;i<=n;i++)
        C[0][i]=C[i+n][2*n+1]=1;
    double st,dr,med,last,last_pd;
    st=0;dr=10000.0;last=dr;
    while(dr-st>0.0001)
    {
        med=(st+dr)*0.5;
        double pd=MaxFlowMinCost(med);
        if(pd<0)
            st=med+0.0001;
        else
        {
            last=med;last_pd=pd;
            dr=med-0.0001;
        }
    }
    printf("%.5lf %.5lf\n",last,last_pd);
    return 0;
}