Jewels

题意：

你的坐标是(0,0,0)，有m个宝物，分别坐标是是(xi,yi,zi),它的z坐标以每秒下沉vi深度，你每次获取一个宝物的费用是两者的距离的平方，每秒只能获取一个宝物，从第0秒开始，问获取所有宝物的最小费用

题解：

很明显，所有宝物肯定都在0~n-1这n个时刻被挖掉。
对于每个时间，都有m个宝物，这不久似乎一个最小权匹配问题，一边是时刻，一边是宝物，边权就是该时间的宝物费用
跑遍KM就出来了
KM要用bfs的

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
ll read() {ll x = 0, f = 1; char ch = getchar();for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');return x * f;
}
const int MAXN = 505;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, vx[MAXN], vy[MAXN], px[MAXN], py[MAXN], pre[MAXN];
ll e[MAXN][MAXN], lx[MAXN], ly[MAXN], slack[MAXN];
queue<int> que;
void aug(int v) {while(v) {int t = px[pre[v]];px[pre[v]] = v;py[v] = pre[v];v = t;}
}
void bfs(int s) {for(int i = 1; i <= n; i++) vx[i] = vy[i] = 0, slack[i] = INF;que = queue<int>();que.push(s);while(1) {while(que.size()) {int u = que.front(); que.pop();vx[u] = 1;for(int v = 1; v <= n; v++) if(!vy[v]) {if(lx[u] + ly[v] - e[u][v] < slack[v]) {slack[v] = lx[u] + ly[v] - e[u][v];pre[v] = u;if(slack[v] == 0) {vy[v] = 1;if(!py[v]) {aug(v); return ;}else que.push(py[v]);}}}}ll d = INF;for(int i = 1; i <= n; i++) if(!vy[i]) d = min(d, slack[i]);for(int i = 1; i <= n; i++) {if(vx[i]) lx[i] -= d;if(vy[i]) ly[i] += d;else slack[i] -= d;}for(int i = 1; i <= n; i++) if(!vy[i]) {if(slack[i] == 0) {vy[i] = 1;if(!py[i]) {aug(i); return ;}else que.push(py[i]);}}}
}
void KM() {for(int i = 1; i <= n; i++) lx[i] = -INF, ly[i] = 0;for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) lx[i] = max(lx[i], e[i][j]);for(int i = 1; i <= n; i++) bfs(i);
}
void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen("J.txt","r",stdin);#endif
}
ll dis(ll x,ll y,ll z){return x*x+y*y+z*z;
}
ll x[400],y[400],z[400],v[400];
int main() {rd_txt();cin>>n;m = n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++) e[i][j] = -INF;for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>z[i]>>v[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){e[i][j]=-1ll*dis(x[j],y[j],z[j]+1ll*(i-1)*v[j]);}}KM();ll ans = 0;for(int i = 1; i <= n; i++) ans += lx[i] + ly[i];printf("%lld\n", -1*ans);return 0;
}