北京游戏网站建设,百度安装下载,推广普通话手抄报内容大全,荆州建设局网站Jewels
题意#xff1a;
你的坐标是(0,0,0)#xff0c;有m个宝物#xff0c;分别坐标是是(xi,yi,zi),它的z坐标以每秒下沉vi深度#xff0c;你每次获取一个宝物的费用是两者的距离的平方#xff0c;每秒只能获取一个宝物#xff0c;从第0秒开始#xff0c;问获取所有宝…Jewels
题意
你的坐标是(0,0,0)有m个宝物分别坐标是是(xi,yi,zi),它的z坐标以每秒下沉vi深度你每次获取一个宝物的费用是两者的距离的平方每秒只能获取一个宝物从第0秒开始问获取所有宝物的最小费用
题解
很明显所有宝物肯定都在0~n-1这n个时刻被挖掉。 对于每个时间都有m个宝物这不久似乎一个最小权匹配问题一边是时刻一边是宝物边权就是该时间的宝物费用 跑遍KM就出来了 KM要用bfs的
代码
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includeiostream
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];
queueint 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 queueint();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*xy*yz*z;
}
ll x[400],y[400],z[400],v[400];
int main() {rd_txt();cinn;m n;for(int i 1; i n; i)for(int j 1; j n; j) e[i][j] -INF;for(int i1;in;i)cinx[i]y[i]z[i]v[i];for(int i1;in;i){for(int j1;jn;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;
}
