[海军国际项目办公室]欢乐豆

2024-03-16 22:38

本文主要是介绍[海军国际项目办公室]欢乐豆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

欢乐豆

题目概述

在这里插入图片描述
在这里插入图片描述

题解

首先可以发现一个性质,我们到任意一个未被更改所影响的节点上,不可能经过超过一条更改的边。
显然,如果我中途需要经过一条未被修改的边,那么我一定可以在从这个点的出发点直接走这条边到达这个点,如果到其它点再走,那么我所需要走的边权肯定会更大。
于是,到任意一个未被更改所影响的节点上,未被更改的节点直接走 a i a_{i} ai的边就行了。而一个被更改所影响了的节点,则需要可以沿着最短路走到某个节点,再从那个节点走 a i a_{i} ai的边。
剩下的更改过的节点走到更改过的节点的最短路,与我们上面的目的是相仿的,所以事实上我们真正的难点就是求这个最短路。

如果你直接用 F l o y e d Floyed Floyed找最短路的话,是 O ( m 3 ) O\left(m^3\right) O(m3)的,只有 36 p t s 36pts 36pts,最多再加上一个可以直接 d i j dij dij的特殊性质 B B B
但实际上我们可以用线段树来模拟 d i j dij dij
我们对于每个点出发都做一次 d i j dij dij,更新到每个节点的最短路是用该节点去更新未被更新的节点的最短路。
我们发现,从一个点出发,只有到与它之间连边是被更改过的情况边权是独特的,否则边权都是 a i a_{i} ai
所以我们可以对于这些独特的边单点修改,对于其它点区间修改。
还有跳出去到未被更改的点再跳回来的情况,这种情况可以全局修改。
即使其它点的区间不一定是连续的,但由于我们的独特点只有 O ( m ) O(m) O(m)个,所以我们区间修改的区间也是 O ( m ) O(m) O(m)级别的。
所以做一次 d i j dij dij实际上是 O ( m log ⁡ m ) O\left(m\log\,m\right) O(mlogm)的。啊啊啊!!!
直接对于每个点都做一次 d i j dij dij就行了。

时间复杂度 O ( n + m 2 log ⁡ m ) O\left(n+m^2\log\,m\right) O(n+m2logm)

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 6005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;   
const int mo=5e5+9;
const int inv2=499122177;
const double jzm=0.997;
const int zero=15;
const int lim=2500000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,m,a[MAXN],id[MAXN],ord[MAXM],idx;
int mna,val[MAXM],dis[MAXN];
bool key[MAXN];LL ans;
vector<pii>G[MAXM];
struct ming{int u,v,w;}s[MAXM];
bool cmp(int x,int y){return val[x]<val[y];}
class SegmentTree{private:int minn[MAXM<<2],lzy[MAXM<<2],maxx[MAXM<<2];bool cov[MAXM<<2];void pushup(int rt){minn[rt]=INF;cov[rt]=cov[lson]&cov[rson];maxx[rt]=0;if(!cov[lson])minn[rt]=min(minn[lson],minn[rt]),maxx[rt]=max(maxx[lson],maxx[rt]);if(!cov[rson])minn[rt]=min(minn[rson],minn[rt]),maxx[rt]=max(maxx[rson],maxx[rt]);}void pushdown(int rt){if(lzy[rt]<INF-1){if(!cov[lson])maxx[lson]=lzy[rt],minn[lson]=min(lzy[rt],minn[lson]),lzy[lson]=min(lzy[lson],lzy[rt]);if(!cov[rson])maxx[rson]=lzy[rt],minn[rson]=min(lzy[rt],minn[rson]),lzy[rson]=min(lzy[rson],lzy[rt]);lzy[rt]=INF;}}public:void build(int rt,int l,int r){maxx[rt]=minn[rt]=lzy[rt]=INF;cov[rt]=0;if(l==r)return ;int mid=l+r>>1;build(lson,l,mid);build(rson,mid+1,r);}void modify(int rt,int l,int r,int al,int ar,int aw){if(l>r||l>ar||r<al||al>ar||cov[rt])return ;if(al<=l&&r<=ar){minn[rt]=min(aw,minn[rt]);maxx[rt]=aw;lzy[rt]=min(lzy[rt],aw);return ;}int mid=l+r>>1;pushdown(rt);if(al<=mid)modify(lson,l,mid,al,ar,aw);if(ar>mid)modify(rson,mid+1,r,al,ar,aw);pushup(rt);}pii query(int rt,int l,int r){if(l==r)return mkpr(minn[rt],l);int mid=l+r>>1;pushdown(rt);if(!cov[lson]&&minn[lson]<=minn[rson])return query(lson,l,mid);return query(rson,mid+1,r);}void update(int rt,int l,int r,int ai){if(l>r||l>ai||r<ai)return ;if(l==r){minn[rt]=maxx[rt]=INF;cov[rt]=1;return ;}int mid=l+r>>1;pushdown(rt);if(ai<=mid)update(lson,l,mid,ai);if(ai>mid)update(rson,mid+1,r,ai);pushup(rt); } int queryMax(){return maxx[1];}
}T;
signed main(){freopen("happybean.in","r",stdin);freopen("happybean.out","w",stdout); read(n);read(m);mna=INF;for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=m;i++){read(s[i].u),read(s[i].v);read(s[i].w);key[s[i].u]=key[s[i].v]=1;}for(int i=1;i<=n;i++)if(key[i])ord[++idx]=i,id[i]=idx;for(int i=1;i<=m;i++)G[id[s[i].u]].pb(mkpr(id[s[i].v],s[i].w));for(int i=1;i<=idx;i++)sort(G[i].begin(),G[i].end());for(int i=1;i<=n;i++)if(!key[i])mna=min(mna,a[i]);for(int i=1;i<=n;i++){if(!key[i]){ans+=1ll*a[i]*(n-1);continue;}T.build(1,1,idx);T.modify(1,1,idx,id[i],id[i],0);int minn=INF;for(int j=1;j<=idx;j++){pii t=T.query(1,1,idx);int u=t.sec;int siz=G[u].size(),las=0;dis[u]=t.fir;if(dis[u]<T.queryMax()){for(int k=0;k<siz;k++){int v=G[u][k].fir,w=G[u][k].sec;T.modify(1,1,idx,las+1,v-1,dis[u]+a[ord[u]]);T.modify(1,1,idx,v,v,dis[u]+w);las=v;}T.modify(1,1,idx,las+1,idx,dis[u]+a[ord[u]]);T.modify(1,1,idx,1,idx,dis[u]+a[ord[u]]+mna);}T.update(1,1,idx,u);ans+=1ll*dis[u];minn=min(minn,dis[u]+a[ord[u]]);}ans+=1ll*minn*(n-idx);}printf("%lld\n",ans);return 0;
}

谢谢!!!

这篇关于[海军国际项目办公室]欢乐豆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816956

相关文章

springboot项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

将Java项目提交到云服务器的流程步骤

《将Java项目提交到云服务器的流程步骤》所谓将项目提交到云服务器即将你的项目打成一个jar包然后提交到云服务器即可,因此我们需要准备服务器环境为:Linux+JDK+MariDB(MySQL)+Gi... 目录1. 安装 jdk1.1 查看 jdk 版本1.2 下载 jdk2. 安装 mariadb(my

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

springboot项目中常用的工具类和api详解

《springboot项目中常用的工具类和api详解》在SpringBoot项目中,开发者通常会依赖一些工具类和API来简化开发、提高效率,以下是一些常用的工具类及其典型应用场景,涵盖Spring原生... 目录1. Spring Framework 自带工具类(1) StringUtils(2) Coll

Spring Boot项目部署命令java -jar的各种参数及作用详解

《SpringBoot项目部署命令java-jar的各种参数及作用详解》:本文主要介绍SpringBoot项目部署命令java-jar的各种参数及作用的相关资料,包括设置内存大小、垃圾回收... 目录前言一、基础命令结构二、常见的 Java 命令参数1. 设置内存大小2. 配置垃圾回收器3. 配置线程栈大小

Spring Boot项目中结合MyBatis实现MySQL的自动主从切换功能

《SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能》:本文主要介绍SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能,本文分步骤给大家介绍的... 目录原理解析1. mysql主从复制(Master-Slave Replication)2. 读写分离3.

一文教你如何将maven项目转成web项目

《一文教你如何将maven项目转成web项目》在软件开发过程中,有时我们需要将一个普通的Maven项目转换为Web项目,以便能够部署到Web容器中运行,本文将详细介绍如何通过简单的步骤完成这一转换过程... 目录准备工作步骤一:修改​​pom.XML​​1.1 添加​​packaging​​标签1.2 添加

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

springboot集成Deepseek4j的项目实践

《springboot集成Deepseek4j的项目实践》本文主要介绍了springboot集成Deepseek4j的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录Deepseek4j快速开始Maven 依js赖基础配置基础使用示例1. 流式返回示例2. 进阶

SpringBoot项目启动报错"找不到或无法加载主类"的解决方法

《SpringBoot项目启动报错找不到或无法加载主类的解决方法》在使用IntelliJIDEA开发基于SpringBoot框架的Java程序时,可能会出现找不到或无法加载主类com.example.... 目录一、问题描述二、排查过程三、解决方案一、问题描述在使用 IntelliJ IDEA 开发基于