Cod sursa(job #1724015)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 2 iulie 2016 00:37:06
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.23 kb
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define MAXN 410
#define EPS 1e-7
#define INF 1000000000
#define x first
#define y second
using namespace std;
queue<int> Queue;
pair<double,double> soldier[2*MAXN],shelter[2*MAXN];
vector<double> distances;
vector<int> g[2*MAXN];
double cost[2*MAXN][2*MAXN],best[2*MAXN],limit;
bool inQueue[2*MAXN],capacity[2*MAXN][2*MAXN],seen[2*MAXN];
char flow[2*MAXN][2*MAXN];
int n,dad[2*MAXN],leftPair[2*MAXN],rightPair[2*MAXN];
int Compare(double a,double b){
    if(a-b>EPS)
        return 1;
    if(a-b<-EPS)
        return -1;
    return 0;
}
bool Match(int node){
    int i;
    if(seen[node]==1)
        return false;
    seen[node]=1;
    for(i=1;i<=n;i++)
        if(Compare(cost[node][n+i],limit)<=0&&rightPair[i]==0){
            rightPair[i]=node;
            leftPair[node]=i;
            return true;
        }
    for(i=1;i<=n;i++)
        if(Compare(cost[node][n+i],limit)<=0&&Match(rightPair[i])==true){
            rightPair[i]=node;
            leftPair[node]=i;
            return true;
        }
    return false;
}
bool MaximumMatching(){
    int ok=1,i;
    memset(leftPair,0,sizeof(leftPair));
    memset(rightPair,0,sizeof(rightPair));
    while(ok==1){
        memset(seen,0,sizeof(seen));
        ok=0;
        for(i=1;i<=n;i++)
            if(leftPair[i]==0&&Match(i)==true)
                ok=1;
    }
    for(i=1;i<=n;i++)
        if(leftPair[i]==0)
            return false;
    return true;
}
double BinarySearch(){
    int left=0,right=n*n,middle,answer;
    while(left<=right){
        middle=(left+right)/2;
        limit=distances[middle];
        if(MaximumMatching()==true){
            answer=middle;
            right=middle-1;
        }
        else
            left=middle+1;
    }
    return distances[answer];
}
bool BellmanFord(){
    int i,node;
    memset(inQueue,0,sizeof(inQueue));
    memset(dad,0,sizeof(dad));
    for(i=1;i<=2*n+1;i++)
        best[i]=INF;
    inQueue[0]=1;
    best[0]=0;
    Queue.push(0);
    while(!Queue.empty()){
        node=Queue.front();
        Queue.pop();
        inQueue[node]=0;
        for(i=0;i<g[node].size();i++)
            if(capacity[node][g[node][i]]>flow[node][g[node][i]]&&Compare(cost[node][g[node][i]],limit)<=0)
                if(Compare(best[g[node][i]],best[node]+cost[node][g[node][i]])>0){
                    best[g[node][i]]=best[node]+cost[node][g[node][i]];
                    dad[g[node][i]]=node;
                    if(inQueue[g[node][i]]==0){
                        inQueue[g[node][i]]=1;
                        Queue.push(g[node][i]);
                    }
                }
    }
    if(dad[2*n+1]!=0)
        return true;
    return false;
}
double MaximumFlow(){
    int i;
    double answer=0;
    while(BellmanFord()==true)
        for(i=2*n+1;i!=0;i=dad[i]){
            flow[dad[i]][i]++;
            flow[i][dad[i]]--;
            answer+=cost[dad[i]][i];
        }
    return answer;
}
int main(){
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    int i,j;
    double current,sum,answer;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&soldier[i].x,&soldier[i].y);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&shelter[i].x,&shelter[i].y);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            current=sqrt((soldier[i].x-shelter[j].x)*(soldier[i].x-shelter[j].x)+(soldier[i].y-shelter[j].y)*(soldier[i].y-shelter[j].y));
            distances.push_back(current);
            cost[i][j+n]=current;
            cost[j+n][i]=-current;
        }
    sort(distances.begin(),distances.end());
    answer=BinarySearch();
    for(i=1;i<=n;i++){
        capacity[0][i]=1;
        g[0].push_back(i);
        g[i].push_back(0);
        capacity[i+n][2*n+1]=1;
        g[2*n+1].push_back(i+n);
        g[i+n].push_back(2*n+1);
        for(j=n+1;j<=2*n;j++)
            if(Compare(cost[i][j],answer)<=0){
                g[i].push_back(j);
                g[j].push_back(i);
                capacity[i][j]=1;
            }
    }
    limit=answer;
    sum=MaximumFlow();
    printf("%.10f %.10f",answer,sum);
    return 0;
}