Cod sursa(job #478060)

Utilizator freak93Adrian Budau freak93 Data 17 august 2010 12:35:46
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#define x first
#define y second

using namespace std;

const char iname[]="adapost.in";
const char oname[]="adapost.out";
const int maxn=805;
const double inf=1e25;

ifstream f(iname);
ofstream g(oname);

pair<double,double> a[maxn],b[maxn];
double cost[maxn][maxn],dis[maxn],m[maxn*maxn],disd;
int n,i,j,k,p,A[maxn],been[maxn],S=0,D=maxn-1,C[maxn][maxn],F[maxn][maxn],step,flow;
queue<int> Q;
vector<int> E[maxn];

bool BF()
{
    memset(been,0,sizeof(been));
    memset(A,-1,sizeof(A));
    dis[S]=0;
    been[S]=1;
    Q.push(S);
    A[S]=S;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        if(x==D)
            continue;
        been[x]=0;
        for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
            if(C[x][*it]>F[x][*it])
                if(A[*it]==-1||dis[x]+cost[x][*it]<dis[*it])
                {
                    dis[*it]=dis[x]+cost[x][*it];
                    A[*it]=x;
                    if(been[*it]==0)
                        been[*it]=1,Q.push(*it);
                }
    }
    return (A[D]!=-1);
}

double dist(pair<double,double> a,pair<double,double> b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    for(i=1;i<=n;++i)
        f>>b[i].x>>b[i].y;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            cost[i][j+n]=-(cost[j+n][i]=-dist(a[i],b[j])),C[i][j+n]=1,m[++k]=cost[i][j+n];
    for(i=1;i<=n;++i)
        C[S][i]=1,C[i+n][D]=1,E[S].push_back(i);
    sort(m+1,m+k+1);
    for(step=1;step<k;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=k)
        {
            i+=step;
            for(j=1;j<=n;++j)
                vector<int>().swap(E[j]),vector<int>().swap(E[j+n]),E[j+n].push_back(D);
            for(j=1;j<=n;++j)
                for(p=n+1;p<=n*2;++p)
                    if(cost[j][p]<=m[i])
                        E[j].push_back(p),E[p].push_back(j);
            memset(F,0,sizeof(F));
            flow=0,disd=0;
            while(BF())
            {
                ++flow,disd+=dis[D];
                for(j=D;j!=S;j=A[j])
                    ++F[A[j]][j],--F[j][A[j]];
            }
            if(flow==n)
                i-=step;
        }
    ++i;
    disd=0;
    for(j=1;j<=n;++j)
        vector<int>().swap(E[j]),vector<int>().swap(E[j+n]),E[j+n].push_back(D);
    for(j=1;j<=n;++j)
        for(p=n+1;p<=n*2;++p)
            if(cost[j][p]<=m[i])
                E[j].push_back(p),E[p].push_back(j);
    memset(F,0,sizeof(F));
    while(BF())
    {
        disd+=dis[D];
        for(j=D;j!=S;j=A[j])
                    ++F[A[j]][j],--F[j][A[j]];
    }
    g.setf(ios::fixed,ios::floatfield);
    g.precision(5);
    g<<m[i]<<" "<<disd<<"\n";
}