Cod sursa(job #478077)

Utilizator freak93Adrian Budau freak93 Data 17 august 2010 12:58:08
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 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,l[maxn],r[maxn],ok;
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 comb(int x)
{
    if(been[x])
        return 0;
    been[x]=1;
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(r[*it]==0)
        {
            l[x]=*it,r[*it]=x;
            return 1;
        }
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(comb(r[*it]))
        {
            l[x]=*it,r[*it]=x;
            return 1;
        }
    return 0;
}

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]);
            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);
            memset(l,0,sizeof(l));
            memset(r,0,sizeof(r));
            flow=0;
            do
            {
                ok=0;
                memset(been,0,sizeof(been));
                for(j=1;j<=n;++j)
                    if(l[j]==0)
                        ok+=comb(j);
                flow+=ok;
            }while(ok);
            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));
    flow=0;
    while(flow<n)
    {
        disd+=dis[D];
        for(j=D;j!=S;j=A[j])
            ++F[A[j]][j],--F[j][A[j]];
        ++flow;
    }
    g.setf(ios::fixed,ios::floatfield);
    g.precision(5);
    g<<m[i]<<" "<<disd<<"\n";
}