【BZOJ3714】[PA2014]Kuglarz 最小生成树
2024-09-25 07:51:32
【BZOJ3714】[PA2014]Kuglarz
Description
魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费c_ij元,魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?
Input
第一行一个整数n(1<=n<=2000)。
第i+1行(1<=i<=n)有n+1-i个整数,表示每一种询问所需的花费。其中c_ij(对区间[i,j]进行询问的费用,1<=i<=j<=n,1<=c_ij<=10^9)为第i+1行第j+1-i个数。
Output
输出一个整数,表示最少花费。
Sample Input
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
Sample Output
7
题解:是不是一告诉你正解是最小生成树你就会做了?
由于询问的是区间和,我们将它转化为两个前缀和相减的形式,那么只要知道了[1,i-1],[1,j],[i,j]中的两个,就能得到第三个。所以连一条(i-1,j)的边,跑最小生成树就行了
由于是完全图,所以理论上应该跑prim,但是我Kruskal16s水过~
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int f[2010];
long long ans;
struct edge
{
int pa,pb;
long long len;
}p[2000010];
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
bool cmp(edge a,edge b)
{
return a.len<b.len;
}
int main()
{
scanf("%d",&n);
int i,j,a,b;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
p[++m].pa=i-1,p[m].pb=j,scanf("%lld",&p[m].len);
sort(p+1,p+m+1,cmp);
for(i=1;i<=n;i++) f[i]=i;
for(i=1,j=0;i<=m;i++)
{
a=find(p[i].pa),b=find(p[i].pb);
if(a!=b)
{
f[a]=b,ans+=p[i].len,j++;
if(j==n)
{
printf("%lld",ans);
return 0;
}
}
}
}
最新文章
- Atitit 图像处理的摩西五经attilax总结
- 关于Django 错误 查询之后结果序列化出现的问题is not JSON serializable
- sublime编辑器插件
- redis中使用redis-dump导出、导入、还原数据实例
- [PHP]swoole_server几个进程的分工
- python—命名规范(转)
- HDU1009 FatMouse&#39; Trade
- Ubuntu 系统搭建php服务器 用ssh 远程操作
- python字符串格式化符号含义及转义字符含义
- IOS学习之路(二十五)UIView动画,弹出后移动然后消失
- [SOJ] 商人的宣传
- DJango内建模板转向jinja2的小脚本
- libiconv交叉编译提示arm-none-linux-gnueabi-gcc
- 一: WCF的服务端与客户端在通信时有三种模式:请求响应模式、数据报模式和双工通讯模式。
- Provider Pattern for Beginners in .net
- [LeetCode&;Python] Problem 617. Merge Two Binary Trees
- Java数据结构基础知识你知道多少?
- 单链表是否有环的问题解决与讨论(java实现)
- 洛谷九月月赛II
- js数组最大值和最小值计算
热门文章
- VSCode开发工具下载
- C++的多态例子
- Office 365 离线安装
- 使用 ConfigurationSection 创建自定义配置节
- js setInterval()函数 [倒计时用]
- makefile之origin函数
- 汉诺塔(-) java modPow 的用法;
- Xcode7 beta 网络请求报错:The resource could not be loaded because the App Transport Security policy requir
- tomcat打印GC日志
- 猫猫学iOS 之微博项目实战(5)微博自己定义搜索框searchBar