热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【Codeforces1076D】EdgeDeletion|最短路树

题目大意:给定n,m,k:n个点,m条边,要进行删边操作,最后可以保留最多k条边定义一个点i是好的当且仅当在删除一些边之

 

题目大意:

给定n,m,k:n个点,m条边,要进行删边操作,最后可以保留最多k条边

定义一个点i是好的当且仅当在删除一些边之后,1->i的最短路等于未删边之前的最短路

输出最多可以有多少个好的点,输出保留边的个数与保留边的编号

题目思路:

刚开始看到删边,联想到最短路径还原。

考虑求最短路的过程,可以知道求最短路的过程中一定会存在没有用的一些边即对最短路根本没有影响的边。

如果对于一条边来说满足:dis[s]+w = = dis[e] ,那么s这条边在1 -> e的最短路上

所以首先把不满足这个条件的边删掉

之后考虑剩下的边,显然可见最短路是分层的:

此时,显而易见肯定从后向前删,因为删除过程中的一下子会失去大于等于1个点,而删最后只会失去一个点。

考虑一下拓扑排序或许可以解决这个问题。

但是呢考虑这个边权都是正数,起点又固定,所以最短路按分层来说绝对是距离越来越大,所以只需要排序,保留前k个点即可

wa7..

又随便考虑一下这个问题,发现有一种情况:

基于上面的图,或许会还原出这种情况:

 此时删除点4以为删除2条边,所以可能会出错。

所以去重一下,每一个点只对应一条边,现在来说就可以一个点对应一个权值,然后排序之后保留前k个点,也就保留了前k条边。

注意:

1.这个题因为是d2的,所以绝对有不法份子专门卡spfa【赛时hack机制】,所以建议优化的最短路

2.亲测最短路的值爆了long long 

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<<#x<<":"<using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF&#61;1e17;
const int maxn&#61;1e6&#43;6;
const int mod&#61;998244353;
const double eps&#61;1e-3;
inline bool read(ll &num)
{char in;bool IsN&#61;false;in&#61;getchar();if(in&#61;&#61;EOF) return false;while(in!&#61;&#39;-&#39;&&(in<&#39;0&#39;||in>&#39;9&#39;)) in&#61;getchar();if(in&#61;&#61;&#39;-&#39;){ IsN&#61;true;num&#61;0;}else num&#61;in-&#39;0&#39;;while(in&#61;getchar(),in>&#61;&#39;0&#39;&&in<&#61;&#39;9&#39;){num*&#61;10,num&#43;&#61;in-&#39;0&#39;;}if(IsN) num&#61;-num;return true;}
ll n,m,p;
struct node{int s,e,next;ll w;
}edge[maxn];
ll cnt &#61; 0;
int head[maxn];
void addedge(int u,int v,ll w){edge[cnt]&#61;node{u,v,head[u],w};head[u]&#61;cnt&#43;&#43;;
}
ll dis[maxn];
struct N{int id;ll w;bool friend operator<(N a,N b){return a.w>b.w;}
};
void dijstra(int st)
{for(int i&#61;1;i<&#61;n;i&#43;&#43;) dis[i]&#61;INF;dis[st]&#61;0;N s;s.id&#61;st;s.w&#61;0;priority_queueq;q.push(s);while(!q.empty()){N u&#61;q.top();q.pop();if(dis[u.id]!&#61;u.w) continue;for(int i&#61;head[u.id];~i;i&#61;edge[i].next){int e&#61;edge[i].e;if(dis[e]>u.w&#43;edge[i].w){dis[e]&#61;u.w&#43;edge[i].w;N now;now.id&#61;e;now.w&#61;dis[e];q.push(now);}}}
}
pairsave[maxn];
int visp[maxn];
ll res&#61;0;
void rebuild(){for(int i&#61;0;i}
int main(){memset(head,-1,sizeof(head));read(n);read(m);read(p);for(int i&#61;1;i<&#61;m;i&#43;&#43;){int x,y;ll w;scanf("%d%d%lld",&x,&y,&w);addedge(x,y,w);addedge(y,x,w);}dijstra(1);rebuild();if(p>&#61;res){printf("%lld\n",res);for(int i&#61;1;i<&#61;res;i&#43;&#43;)printf("%d ",save[i].second);}else{printf("%lld\n",p);sort(save&#43;1,save&#43;1&#43;res);for(int i&#61;1;i<&#61;p;i&#43;&#43;)printf("%d ",save[i].second);}printf("\n");return 0;
}
/**
4 5 3
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5**/

 


推荐阅读
  • 在解决区间相关问题时,我发现自己经常缺乏有效的思维方式,即使是简单的题目也常常需要很长时间才能找到解题思路,而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作,并给出一个参数k,具体任务是…… ... [详细]
  • 设计实战 | 10个Kotlin项目深度解析:首页模块开发详解
    设计实战 | 10个Kotlin项目深度解析:首页模块开发详解 ... [详细]
  • 开发心得:成为SGU475智能筏工的策略与技巧 ... [详细]
  • 每日精选Codeforces训练题:1119E(贪心算法)、821C(栈模拟)和645D(拓扑排序)
    题目涉及三种不同类型的算法问题:1119E(贪心算法)、821C(栈模拟)和645D(拓扑排序)。其中,1119E的问题背景是有n种不同长度的棍子,长度分别为2^0, 2^1, …, 2^(n-1),每种棍子的数量为a[i]。任务是计算可以组成的三角形数量。根据三角形的性质,任意两边之和必须大于第三边。该问题可以通过贪心算法高效解决,通过合理选择棍子组合来最大化三角形的数量。 ... [详细]
  • 在2021-2022 ACM集训队月度编程挑战赛第二轮中,题目“最大值与最小值的选择”要求参赛者处理一个包含n个元素的数组,并给定一个整数k。任务是通过选择特定的子数组,计算并返回这些子数组的最大值和最小值之间的差值。该问题考验了选手对数组操作和优化算法的理解与应用能力。 ... [详细]
  • 题目:图像处理(HDU1828,计算周长并集,利用线段树与离散化技术进行扫描) ... [详细]
  • BZOJ 1835: 基站位置选择问题(动态规划与线段树优化) ... [详细]
  • 在HDU 1166敌军布阵问题中,通过运用线段树数据结构,可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解,还能够灵活应对动态变化的战场局势,为实时决策提供支持。 ... [详细]
  • 利用 Spring BeanUtils 实现 JavaBean 的深度克隆与属性复制 ... [详细]
  • C++入门必备:首个博客知识点汇总
    本文总结了C++初学者需要掌握的关键知识点,特别强调了成员类型的区分。其中,protected成员与private成员在本类中的作用相同,但protected成员允许派生类的成员函数访问,而private成员则不允许。此外,文章还介绍了其他重要的C++基础概念,如类的构造函数、析构函数以及继承机制,为初学者提供了一个全面的学习指南。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • Java SE 文件操作类详解与应用
    ### Java SE 文件操作类详解与应用#### 1. File 类##### 1.1 File 类概述File 类是 Java SE 中用于表示文件和目录路径名的对象。它提供了丰富的方法来操作文件和目录,包括创建、删除、重命名文件,以及获取文件属性和信息。通过 File 类,开发者可以轻松地进行文件系统操作,如检查文件是否存在、读取文件内容、列出目录下的文件等。此外,File 类还支持跨平台操作,确保在不同操作系统中的一致性。 ... [详细]
  • 字节码开发笔记:深入解析与应用技巧 ... [详细]
author-avatar
化工12卓越团支部CUP
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有