Cod sursa(job #2448057)

Utilizator CharacterMeCharacter Me CharacterMe Data 15 august 2019 16:09:28
Problema Adapost Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <bits/stdc++.h>
#define pdd pair<double, double>
#define pdi pair<double, int>
#define pii pair<int, int>
#define inf 1000000000
///N=400
using namespace std;
///
int n, i, j, k, s, d, cnt, l, r, mid;
int flow[801][801], last[801], lft[801], rgt[801];
double outone, outall;
double cost[801][801], dmin[801];
pdd plist[801];
pair<double, pii> dlist[801];
vector<int> graph[805];
priority_queue<pdi, vector<pdi>, greater<pdi> > pq;
///
void read();
void solve();
void write();
double calc(pdd node1, pdd node2);
bool dij(double val);
bool CM(double val);
bool dfs(int node);
void refresh(double val, bool ult);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("adapost.in", "r", stdin);
    scanf("%d", &n);
    for(i=1; i<=2*n; ++i) scanf("%lf%lf", &plist[i].first, &plist[i].second);
    fclose(stdin);
    return;
}
void solve(){
    s=0, d=2*n+1;
    for(i=1; i<=n; ++i)
    for(j=n+1; j<=2*n; ++j){
        double dist=calc(plist[i], plist[j]);
        cost[i][j]=dist;
        cost[j][i]=-dist;
        dlist[++cnt].first=dist;
        dlist[cnt].second={i, j};
    }
    sort(dlist+1, dlist+n*n+1);
    l=1; r=n*n;
    while(r-l>1){
        mid=(l+r)/2;
        if(CM(dlist[mid].first)) r=mid;
        else l=mid;
    }
    outone=dlist[r].first;
    refresh(outone, true);
    for(i=1; i<=n; ++i) {
        flow[s][i]=1;
        graph[s].push_back(i);
        graph[i].push_back(s);
        flow[i+n][d]=1;
        graph[i+n].push_back(d);
        graph[d].push_back(i+n);
    }
    while(dij(outone)){
        int p;
        for(p=d; p!=s; p=last[p]){
            --flow[last[p]][p];
            ++flow[p][last[p]];
            outall+=cost[last[p]][p];
        }
    }
    return;
}
void write(){
    freopen("adapost.out", "w", stdout);
    printf("%.5f %.5f", outone, outall);
    return;
}
double calc(pdd node1, pdd node2){
    return sqrt((node1.first-node2.first)*(node1.first-node2.first)+(node1.second-node2.second)*(node1.second-node2.second));
}
bool dij(double val){
    for(i=s; i<=d; ++i) last[i]=-1, dmin[i]=inf;
    dmin[s]=0.0;
    pq.push({0, s});
    while(!pq.empty()){
        double cst=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(node==d) continue;
        if(cst>dmin[node]) continue;
        for(auto next:graph[node]){
            if(!flow[node][next]) continue;
            double nextc=cst+cost[node][next];
            if(nextc<dmin[next]){
                dmin[next]=nextc;
                last[next]=node;
                pq.push({nextc, next});
            }
        }
    }
    return dmin[d]!=inf;
}
bool CM(double val){
    refresh(val, false);
    for(i=1; i<=2*n; ++i) dmin[i]=last[i]=0;
    bool done;
    do{
        done=false;
        for(i=1; i<=n; ++i) if(!dmin[i] && dfs(i)) done=true;
    }while(done);
    done=true;
    for(i=1; i<=n; ++i) if(!dmin[i]) {done=false; break;}
    return done;
}
bool dfs(int node){
    for(auto next:graph[node]) if(!last[next]){
        last[next]=node;
        dmin[node]=next;
        return true;
    }
    for(auto next:graph[node]) if(dfs(last[next])){
        last[next]=node;
        dmin[node]=next;
        return true;
    }
    return false;
}
void refresh(double val, bool ult){
    for(i=1; i<=2*n; ++i) graph[i].clear();
    for(i=1; dlist[i].first<=val; ++i) {
        graph[dlist[i].second.first].push_back(dlist[i].second.second);
        if(ult) {
            graph[dlist[i].second.second].push_back(dlist[i].second.first);
            flow[dlist[i].second.first][dlist[i].second.second]=1;
        }
    }
    return;
}