热门标签 | 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**/

 


推荐阅读
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 题目概述:Sereja 拥有一个由 n 个整数组成的数组 a1, a2, ..., an。他计划执行 m 项操作,这些操作包括更新数组中的特定元素、增加数组中所有元素的值,以及查询数组中的特定元素。 ... [详细]
  • 题目描述:Balala Power! 时间限制:4000/2000 MS (Java/Other) 内存限制:131072/131072 K (Java/Other)。题目背景及问题描述详见正文。 ... [详细]
  • Hanks博士是一位著名的生物技术专家,他的儿子Hankson对数学有着浓厚的兴趣。最近,Hankson遇到了一个有趣的数学问题,涉及求解特定条件下的正整数x,而不使用传统的辗转相除法。 ... [详细]
  • 本文详细介绍如何在SSM(Spring + Spring MVC + MyBatis)框架中实现分页功能。包括分页的基本概念、数据准备、前端分页栏的设计与实现、后端分页逻辑的编写以及最终的测试步骤。 ... [详细]
  • 编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • C/C++ 应用程序的安装与卸载解决方案
    本文介绍了如何使用Inno Setup来创建C/C++应用程序的安装程序,包括自动检测并安装所需的运行库,确保应用能够顺利安装和卸载。 ... [详细]
  • LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题,提供了C++语言的实现代码,并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • Go语言实现文件读取与终端输出
    本文介绍如何使用Go语言编写程序,通过命令行参数指定文件路径,读取文件内容并将其输出到控制台。代码示例中包含了错误处理和资源管理的最佳实践。 ... [详细]
  • D17:C#设计模式之十六观察者模式(Observer Pattern)【行为型】
    一、引言今天是2017年11月份的最后一天,也就是2017年11月30日,利用今天再写一个模式,争取下个月(也就是12月份& ... [详细]
  • 本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程,不仅能够检验开发者对C++基础知识的掌握程度,还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能,如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]
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社区 版权所有