Cod sursa(job #1936674)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 23 martie 2017 11:55:55
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define pb push_back
using namespace std;
const int nmax=823;
int n;
vector<int>adj[nmax];
int sursa,dest,c[nmax][nmax],f[18][nmax][nmax],t[nmax],vis[nmax],pcur,ir;
double soldier[2][nmax],refuge[2][nmax],dist[nmax][nmax],d[nmax],sol;
queue<int>q;
int comp(const int &a,const int &b)
{
    return dist[ir][a]<dist[ir][b];
}
void citire()
{
    scanf("%d",&n);
    dest=2*n+1;
    for(int i=1;i<=n;i++) scanf("%lf%lf",&soldier[0][i],&soldier[1][i]);
    for(int i=1;i<=n;i++)
    {
        c[sursa][i]=1;
        c[i+n][dest]=1;
        adj[sursa].pb(i);
        adj[i].pb(sursa);
        adj[i+n].pb(dest);
        adj[dest].pb(i+n);
        scanf("%lf%lf",&refuge[0][i],&refuge[1][i]);
        for(int j=1;j<=n;j++)
        {
            dist[i][j+n]=sqrt((soldier[0][j]-refuge[0][i])*(soldier[0][j]-refuge[0][i])+(soldier[1][j]-refuge[1][i])*(soldier[1][j]-refuge[1][i]));
            dist[j+n][i]=-dist[i][j+n];
            c[i][j+n]=1;
            adj[i].pb(j+n);
            adj[j+n].pb(i);
        }
    }
    for(ir=sursa;ir<=dest;ir++) sort(adj[ir].begin(),adj[ir].end(),comp);
}
int bellman(double vall)
{
    for(int i=sursa;i<=dest;i++)
    {
        vis[i]=0;
        t[i]=-1;
        d[i]=0x3f3f3f3f;
    }
    q.push(sursa);
    vis[sursa]=1;
    d[sursa]=0;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
       // printf("%d ",nod);
        for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
        {
          //  printf("A");
            if(dist[nod][*it]>vall) break;
            if(c[nod][*it]-f[pcur][nod][*it]<=0) continue;
            if(d[*it]>d[nod]+dist[nod][*it])
            {
                d[*it]=d[nod]+dist[nod][*it];
                t[*it]=nod;
                if(vis[*it]) continue;
                vis[*it]=1;
                q.push(*it);
            }
        }
        vis[nod]=0;
    }
 //   printf("\n");
    if(d[dest]==0x3f3f3f3f) return 0;
    return 1;
}
int do_flow(double val)
{
    int flow=0;
    sol=0;
    while(bellman(val))
    {
        int minim=0x3f3f3f3f;
        for(int i=dest;i!=sursa;i=t[i]) minim=min(minim,c[t[i]][i]-f[pcur][t[i]][i]);
        flow+=minim;
        sol+=minim*d[dest];
        for(int i=dest;i!=sursa;i=t[i])
        {
            f[pcur][t[i]][i]+=minim;
            f[pcur][i][t[i]]-=minim;
        }
    }
    return flow;
}
inline void do_bs()
{
    int st=0,dr=1000000;
    double rasp=0,costperrasp=0;
    while(st<=dr)
    {
        int mij=((st+dr))/2;
        int vrr=do_flow((double)((double)(mij)/1000));
        if(vrr==n)
        {
            rasp=(double)((double)mij)/1000;
            costperrasp=sol;
            dr=mij-1;
        }
        else st=mij+1;
        ++pcur;
    }
    printf("%lf %lf\n",rasp,costperrasp);
}
int main()
{
    freopen ("adapost.in","r",stdin);
    freopen ("adapost.out","w",stdout);
    citire();
    do_bs();
}