Submission #83872

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

struct edge {
    int to;
    int cap;
    double cost;
    int rev;
};

int V;
vector <edge> g[202];
double h[202];
double dist[202];
int prevv[202];
int preve[202];

double d(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1-  y2));
}

void add_edge(int from, int to, int cap, double cost)
{
    g[from].push_back((edge){to, cap, cost, g[to].size()});
    g[to].push_back((edge){from, 0, -cost, g[from].size() - 1});
}

double min_cost_flow(int s, int t, int f)
{
    int i;
    double res = 0;
    
    for (i = 0; i < V; i++) h[i] = 0;
    
    while (f > 0) {
        int d = f;
        priority_queue <pair<double, int> > q;
        
        for (i = 0; i < V; i++) dist[i] = 1e9;
        
        dist[s] = 0;
        
        q.push(make_pair(0, s));
        
        while (!q.empty()) {
            double c = -q.top().first;
            int v = q.top().second;
            
            q.pop();
            
            if (dist[v] < c) continue;
            
            for (i = 0; i < g[v].size(); i++) {
                edge &e = g[v][i];
                
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    q.push(make_pair(-dist[e.to], e.to));
                }
            }
        }
        
        if (dist[t] == 1e9) return -1;
        
        for (i = 0; i < V; i++) h[i] += dist[i];
        
        for (i = t; i != s; i = prevv[i]) d = min(d, g[prevv[i]][preve[i]].cap);
        
        f -= d;
        
        res += d * h[t];
        
        for (i = t; i != s; i = prevv[i]) {
            edge &e = g[prevv[i]][preve[i]];
            e.cap -= d;
            g[i][e.rev].cap += d;
        }
    }
    
    return res;
}

int main()
{
    int n, i, j;
    int a[100][2];
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d %d", &a[i][0], &a[i][1]);
    
    V = n * 2 + 2;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) {
                add_edge(i, n + j, 1, d(a[i][0], a[i][1], 0, a[i][1]));
            } else {
                add_edge(i, n + j, 1, d(a[i][0], a[i][1], -a[j][0], a[j][1]) / 2);
            }
        }
    }
    
    for (i = 0; i < n; i++) {
        add_edge(V - 1, i, 1, 0);
        add_edge(n + i, V - 2, 1, 0);
    }
    
    printf("%.12lf\n", min_cost_flow(V - 1, V - 2, n));
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:96:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:98:63: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result