【传送】

KM

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w[305][305]; // cost matrix
namespace KM {
    ll cal(int n, int m) {
        vector<ll> u(n + 1), v(m + 1), p(m + 1), way(m + 1);
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            ll j0 = 0;
            vector<ll> minv(m + 1, 1e18);
            vector<char> used(m + 1, false);
            do {
                used[j0] = true;
                ll i0 = p[j0], delta = 1e18, j1;
                for (int j = 1; j <= m; ++j) {
                    if (!used[j]) {
                        ll cur = w[i0][j] - u[i0] - v[j];
                        if (cur < minv[j]) {
                            minv[j] = cur, way[j] = j0;
                        }
                        if (minv[j] < delta) {
                            delta = minv[j], j1 = j;
                        }
                    }
                }
                for (int j = 0; j <= m; ++j) {
                    if (used[j]) {
                        u[p[j]] += delta, v[j] -= delta;
                    }
                    else {
                        minv[j] -= delta;
                    }
                }
                j0 = j1;
            } while (p[j0] != 0);
            do {
                ll j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0);
        }
        ll res = 0;
        for (int i = 1; i <= m; i++) {
            res += w[p[i]][i];
        }
        return res;
    }
}

signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int n; cin >> n;
    ll x,y,z,v;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y >> z >> v;
        for (int j = 0; j <= n - 1; j++)
            w[i][j+1]=x*x+y*y+(z+v*j)*(z+v*j);
    }
    cout << KM::cal(n, n) << '\n';
    return 0;
}

最小费用流：

code：

#include <bits/stdc++.h>
using namespace std;
const int N = 607;
namespace atcoder {
    template <class Cap, class Cost> struct mcf_graph {
    public:
        mcf_graph() {}
        mcf_graph(int n) : _n(n), g(n) {}

        int add_edge(int from, int to, Cap cap, Cost cost) {
            assert(0 <= from && from < _n);
            assert(0 <= to && to < _n);
            int m = pos.size();
            pos.push_back({ from, g[from].size() });
            int from_id = g[from].size();
            int to_id = g[to].size();
            if (from == to) to_id++;
            g[from].push_back(_edge{ to, to_id, cap, cost });
            g[to].push_back(_edge{ from, from_id, 0, -cost });
            return m;
        }

        struct edge {
            int from, to;
            Cap cap, flow;
            Cost cost;
        };

        edge get_edge(int i) {
            int m = pos.size();
            assert(0 <= i && i < m);
            auto _e = g[pos[i].first][pos[i].second];
            auto _re = g[_e.to][_e.rev];
            return edge{
                pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
            };
        }
        vector<edge> edges() {
            int m = pos.size();
            vector<edge> result(m);
            for (int i = 0; i < m; i++) {
                result[i] = get_edge(i);
            }
            return result;
        }

        pair<Cap, Cost> flow(int s, int t) {
            return flow(s, t, numeric_limits<Cap>::max());
        }
        pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
            return slope(s, t, flow_limit).back();
        }
        vector<pair<Cap, Cost>> slope(int s, int t) {
            return slope(s, t, numeric_limits<Cap>::max());
        }
        vector<pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
            assert(0 <= s && s < _n);
            assert(0 <= t && t < _n);
            assert(s != t);
            vector<Cost> dual(_n, 0), dist(_n);
            vector<int> pv(_n), pe(_n);
            vector<bool> vis(_n);
            auto dual_ref = [&]() {
                fill(dist.begin(), dist.end(),
                    numeric_limits<Cost>::max());
                fill(pv.begin(), pv.end(), -1);
                fill(pe.begin(), pe.end(), -1);
                fill(vis.begin(), vis.end(), false);
                struct Q {
                    Cost key;
                    int to;
                    bool operator<(Q r) const { return key > r.key; }
                };
                priority_queue<Q> que;
                dist[s] = 0;
                que.push(Q{ 0, s });
                while (!que.empty()) {
                    int v = que.top().to;
                    que.pop();
                    if (vis[v]) continue;
                    vis[v] = true;
                    if (v == t) break;
                    for (int i = 0; i < g[v].size(); i++) {
                        auto e = g[v][i];
                        if (vis[e.to] || !e.cap) continue;
                        Cost cost = e.cost - dual[e.to] + dual[v];
                        if (dist[e.to] - dist[v] > cost) {
                            dist[e.to] = dist[v] + cost;
                            pv[e.to] = v;
                            pe[e.to] = i;
                            que.push(Q{ dist[e.to], e.to });
                        }
                    }
                }
                if (!vis[t]) {
                    return false;
                }

                for (int v = 0; v < _n; v++) {
                    if (!vis[v]) continue;
                    dual[v] -= dist[t] - dist[v];
                }
                return true;
            };
            Cap flow = 0;
            Cost cost = 0, prev_cost_per_flow = -1;
            vector<pair<Cap, Cost>> result;
            result.push_back({ flow, cost });
            while (flow < flow_limit) {
                if (!dual_ref()) break;
                Cap c = flow_limit - flow;
                for (int v = t; v != s; v = pv[v]) {
                    c = min(c, g[pv[v]][pe[v]].cap);
                }
                for (int v = t; v != s; v = pv[v]) {
                    auto& e = g[pv[v]][pe[v]];
                    e.cap -= c;
                    g[v][e.rev].cap += c;
                }
                Cost d = -dual[s];
                flow += c;
                cost += c * d;
                if (prev_cost_per_flow == d) {
                    result.pop_back();
                }
                result.push_back({ flow, cost });
                prev_cost_per_flow = d;
            }
            return result;
        }

    private:
        int _n;

        struct _edge {
            int to, rev;
            Cap cap;
            Cost cost;
        };

        vector<pair<int, int>> pos;
        vector<vector<_edge>> g;
    };

}
using namespace atcoder;
mcf_graph<int64_t, int64_t> mc(N);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,s,t;
    long long x,y,z,v,res(0);
    cin>>n;
    s=0,t=2*n+1;
    for(int i=1;i<=n;++i) {
        cin>>x>>y>>z>>v;
        for(int j=1;j<=n;++j)
            mc.add_edge(j,n+i,1,z*z),z+=v;
        res+=x*x+y*y;
        mc.add_edge(s,i,1,0);
        mc.add_edge(n+i,t,1,0);
    }
    cout<<res+mc.flow(s, t).second<<'\n';
}