题目链接

题意

有n个宝藏在一片三维的海中，每秒可以用钩子捞起一个，每个宝藏有一个垂直向下落的速度，问如何拿使得钩子伸出的距离的平方最小。

分析

每秒只能捞一个，一个宝箱只能在某一秒被捞起，且每秒可以捞任意一个宝箱，每个宝箱也可以在任意秒被捞起，将秒当做左部，宝藏当做右部，边权就是这一秒捞起这个宝藏钩子需要伸出的距离。求最小权匹配即可，用KM算法，将边权取反后计算就算最小值，然后输出时再取反即可，要用bfs的km算法，可以达到$O(n^3)$。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define IO ios::sync_with_stdio(false)
typedef unsigned long long ull;  //卡精度
const int N = 607;               //最多图的点数
const int mod = 1e9 + 7;
const LL INF = 0x3f3f3f3f3f3f3f3f;  //若求最小权值匹配，应该为-1e9+7;
LL w[N][N];              //边权
LL la[N], lb[N];         //左、右部点的顶标
bool va[N], vb[N];        //访问标记，是否在交错树中
int match[N];  //右部点匹配的左部点（一个只能匹配一个嘛）
int n;
LL delta;
int p[N];
LL c[N];//Y中所有不在交错树中的点对于所有在交错树中的X的误差的最小值

void bfs(int x) {
    int a, y = 0, y1 = 0;
    //y记录交错树中最后加入的Y点
    for (int i = 1; i <= n; ++i) p[i] = 0, c[i] = INF;
    match[y] = x;
    do {
        a = match[y], delta = INF, vb[y] = true;
        for (int b = 1; b <= n; ++b) {
            if (!vb[b]) {//不在交错树中的Y点
                if (c[b] > la[a] + lb[b] - w[a][b])//计算最新的误差
                    c[b] = la[a] + lb[b] - w[a][b], p[b] = y;//y是最新加入交错树的点
                if (c[b] < delta)  //还是取最小的
                    delta = c[b], y1 = b;//直接记录最小值对于的Y点
            }
        }
        for (int b = 0; b <= n; ++b)
            if (vb[b])//交错树中的点
                la[match[b]] -= delta, lb[b] += delta;
            else//交错树外的点
                c[b] -= delta;
        y = y1;//y更新成相应的值
    } while (match[y]);//如果y点没有匹配则找到增广路
    while (y) match[y] = match[p[y]], y = p[y];//增广路取反
}

LL KM() {
    for (int i = 0; i <= n; ++i) match[i] = la[i] = lb[i] = 0;
    for (int i = 1; i <= n; ++i) {//对每个点求一次匹配
        for (int j = 0; j <= n; ++j) vb[j] = false;//重新建立增广路
        bfs(i);
    }
    LL res = 0;
    for (int y = 1; y <= n; ++y)  //若匹配失败w[match[y]][y]=INF;
        if(match[y]) res += w[match[y]][y];
    return res;
}
int main(int argc, char const *argv[]) {
    cin >> n;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        LL x, y, z, v;
        cin >> x >> y >> z >> v;
        ans += x * x + y * y;
        for (int j = 0; j < n; j++) {
            w[i][j+1] = -pow(z + v * j, 2);
        }
    }
    cout << ans - KM() << endl;
    return 0;
}