Cod sursa(job #1166176)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 3 aprilie 2014 12:30:42
Problema Adapost Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<fstream>
#include<list>
#include<vector>
#include<bitset>
#include<cmath>
#include<algorithm>
#define DMAX 402
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin ("adapost.in");
ofstream fout("adapost.out");
list<int> lista;
list<int>::iterator it;
vector< list<int> > l(DMAX,lista);
bitset<DMAX>viz;
struct coord{double x,y;}cs[DMAX],ca[DMAX];
int n,i,j,s,d;
int dad[DMAX];
int cap[DMAX][DMAX],flx[DMAX][DMAX],que[DMAX];
double cst[DMAX][DMAX],dst[DMAX],dmax,sumd,c;

double calc_dist(int i, int j)
{
    double d;
    d=sqrt((cs[i].x-ca[j].x)*(cs[i].x-ca[j].x)+(cs[i].y-ca[j].y)*(cs[i].y-ca[j].y));
    return d;
}

int bf()
{
    int ls=0,ld=0,x,y;
    for(i=0;i<=d;++i)
    {
        dst[i]=INF;
        dad[i]=0;
    }
    viz=0;
    dst[s]=1;
    viz[s]=0;
    que[0]=s;
    while(ls<=ld)
    {
        x=que[ls++];
        viz[x]=0;
        for(it=l[x].begin();it!=l[x].end();++it)
        {
            y=*it;
            c=cst[x][y];
            if(dst[y]-dst[x]-c>0.005 && cap[x][y]>flx[x][y])
            {
                dst[y]=dst[x]+c;
                dad[y]=x;
                if(!viz[y])
                {
                    viz[y]=1;
                    que[++ld]=y;
                }
            }
        }
    }
    if(dst[d]<INF)
    {
        int flow=INF;
        for(i=d;i>0;i=dad[i])
            flow=min(flow,cap[dad[i]][i]-flx[dad[i]][i]);
        if(flow!=INF)
        {
            for(i=d;i>0;i=dad[i])
            {
                flx[dad[i]][i]+=flow;
                flx[i][dad[i]]-=flow;
                sumd+=flow*cst[dad[i]][i];
                dmax=max(dmax,flow*cst[dad[i]][i]);
            }
        }
        return 1;
    }
    return 0;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>cs[i].x>>cs[i].y;
    for(i=1;i<=n;++i)
        fin>>ca[i].x>>ca[i].y;
    s=0; d=n+n+1;
    for(i=1;i<=n;++i)
    {
        l[s].push_back(i);
        l[i].push_back(s);
        cap[0][i]=1;
    }
    for(i=n+1;i<d;++i)
    {
        l[i].push_back(d);
        l[d].push_back(i);
        cap[i][d]=1;
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        {
            l[i].push_back(j+n);
            l[j+n].push_back(i);
            cst[i][j+n]=calc_dist(i,j);
            cst[j+n][i]=-cst[i][j+n];
            cap[i][j+n]=1;
        }
    while(bf())
    {

    }
    fout<<dmax<<" "<<sumd;
    return 0;
}