Jewels

題意：

你的坐標是(0,0,0)，有m個寶物，分別坐標是是(xi,yi,zi),它的z坐標以每秒下沉vi深度，你每次獲取一個寶物的費用是兩者的距離的平方，每秒只能獲取一個寶物，從第0秒開始，問獲取所有寶物的最小費用

題解：

很明顯，所有寶物肯定都在0~n-1這n個時刻被挖掉。
對于每個時間，都有m個寶物，這不久似乎一個最小權(quán)匹配問題，一邊是時刻，一邊是寶物，邊權(quán)就是該時間的寶物費用
跑遍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; }

總結(jié)

以上是生活随笔為你收集整理的Jewels的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。