当前位置:网站首页>2021牛客暑期多校训练营5 J Jewels
2021牛客暑期多校训练营5 J Jewels
2022-08-11 11:34:00 【Here_SDUT】
题意
有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;
}
边栏推荐
- HyperLynx(五)反射仿真
- Azure IoT & NVIDIA Jetson 开发基础
- Five minutes to teach you intranet penetration
- Notes and Recommendations for Using Logs
- Small target stunt | Complete the small target detection upgrade of Yolov5 in the easiest way!
- SD8016原厂单电池锂离子电池和锂聚合物电池充电IC
- fiddler双向认证
- 「开源推荐」一个通用的后台管理系统
- AWS、Splunk和Symantec牵头成立OCSF开放网络安全架构框架
- Through the thermal lens focus on different types of gaussian model
猜你喜欢
What areas of the deep neural network are related to the human brain neural network?
嵌入式开发:提示和技巧——退出时休眠
如何用100元制作一块全志V853的AI 开发板
【医学统计学】二项分布
从零开始配置 vim(12)——主题配置
C# Call AutoNavi Map API to obtain latitude, longitude and positioning [Detailed 4D explanation with complete code]
How long does it take to train a neural network, neural network training takes too long
Through the thermal lens focus on different types of gaussian model
centos linux 下安装mysql 8.0
Analyzes how Flink task than YARN container memory limit
随机推荐
资本市场做好为工业互联网“买单”的准备了吗?
TiSpark 原理之下推丨TiDB 工具分享
Go编译原理系列10(逃逸分析)
Neural network visualization has 3 d version of the, the United States to fall!(open source)
Through the thermal lens focus on different types of gaussian model
如何在游戏中实现一场下雨效果
巧用自定义函数,文本控件秒变高速缓存
Tool_RE_IDA基础字符串修改
微信小游戏是个人尝试做游戏最好的选择
2022 OceanBase 年度发布会:发布四大策略,迈入4.0时代
【项目篇- 项目团队部分怎么写、如何作图?(两千字图文总结建议)】创新创业竞赛项目计划书、新苗国创(大创)申报书、挑战杯创业计划竞赛
leetcode:373. 查找和最小的 K 对数字
【2022】【Thesis Notes】Ultra-thin THz deflection based on laser direct writing graphene oxide paper——
scala 高级
Volatile关键字的作用
Uber的20万容器实践:如何避免容器化环境中的 CPU 节流
MySQL --- 存储引擎
沃土云创计划重磅来袭
如何用100元制作一块全志V853的AI 开发板
MySQL --- storage engine