博客
关于我
CodeForces - 1076D Edge Deletion(最短路径树 / dijkstra+贪心)
阅读量:610 次
发布时间:2019-03-12

本文共 4041 字,大约阅读时间需要 13 分钟。

题目链接:

题目大意:

给一个 n n n 个点, m m m 条边的无向简单带权连通图, 要求删边至最多剩余 k k k 条边.
定义"好点"是指删边后, 1 1 1 号节点到它的最短路长度仍然等于原图最短路长度的节点.
最大化删边后的好点个数

题目分析:

思路1:
d i j k s t r a dijkstra dijkstra 算法建出最短路径树,在树上跑 k k k 条边一定符合答案的最优性,因为每加一条树上的边就会多保留一个点,所以直接 b f s bfs bfs 跑一下就可以了
思路2:
因为要保证每加一条边尽可能的多一个点,而 d i j k s t r a dijkstra dijkstra 算法就是一个贪心的过程,所以可以累计 k k k 次松弛操作,这 k k k 条边一定是最优的

具体细节见代码:

思路一:最短路径树

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long#define inf 0x3f3f3f3f#define int llusing namespace std;int read(){ int res = 0,flag = 1; char ch = getchar(); while(ch<'0' || ch>'9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch>='0' && ch<='9') { res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0'; ch = getchar(); } return res*flag;}const int maxn = 3e5+5;const int mod = 1e9+7;const double pi = acos(-1);const double eps = 1e-8;struct Edge { int nxt,to,val,id;}edge[maxn<<1];int n,m,k,head[maxn],cnt,dis[maxn],pre[maxn],id[maxn]; //id[i]表示扩展到i的边的编号 bool vis[maxn];void addedge(int from,int to,int val,int id){ edge[++cnt].nxt = head[from]; edge[cnt].to = to; edge[cnt].val = val; edge[cnt].id = id; head[from] = cnt;}void dijkstra(int u){ priority_queue
,vector
>,greater
>>qu; memset(dis,inf,sizeof(dis)); dis[u] = 0; qu.push(make_pair(0,u)); while(!qu.empty()) { int h = qu.top().second; qu.pop(); if(vis[h]) continue; vis[h] = true; for(int i = head[h];i;i = edge[i].nxt) { int to = edge[i].to,val = edge[i].val; if(dis[to] == dis[h]+val && edge[pre[to]].val > val) { pre[to] = h; id[to] = edge[i].id; } if(dis[to] > dis[h]+val) { pre[to] = h; id[to] = edge[i].id; dis[to] = dis[h]+val; qu.push(make_pair(dis[to],to)); } } }}vector
nod[maxn],e;void bfs(int u){ queue
qu; qu.push(u); while(!qu.empty() && (int)e.size() <= k) { int h = qu.front(); qu.pop(); e.push_back(id[h]); for(auto to : nod[h]) qu.push(to); }}signed main(){ n = read(),m = read(),k = read(); for(int i = 1;i <= m;i++) { int from = read(),to = read(),val = read(); addedge(from,to,val,i); addedge(to,from,val,i); } dijkstra(1); for(int i = 2;i <= n;i++) //建树 nod[pre[i]].push_back(i); bfs(1); printf("%d\n",(int)e.size()-1); for(int i = 1;i < (int)e.size();i++) printf("%d ",e[i]); return 0;}

思路二: d i j k s t r a dijkstra dijkstra 算法+贪心

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long#define inf 0x3f3f3f3f#define int llusing namespace std;int read(){ int res = 0,flag = 1; char ch = getchar(); while(ch<'0' || ch>'9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch>='0' && ch<='9') { res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0'; ch = getchar(); } return res*flag;}const int maxn = 3e5+5;const int mod = 1e9+7;const double pi = acos(-1);const double eps = 1e-8;struct Edge { int nxt,to,val,id;}edge[maxn<<1];int n,m,k,head[maxn],cnt,dis[maxn],pre[maxn],id[maxn]; //id[i]表示扩展到i的边的编号 bool vis[maxn];void addedge(int from,int to,int val,int id){ edge[++cnt].nxt = head[from]; edge[cnt].to = to; edge[cnt].val = val; edge[cnt].id = id; head[from] = cnt;}vector
e;struct node{ int dis,to,id; node(int a,int b,int c) { dis = a,to = b,id = c; } bool operator < (const node &b)const { return dis > b.dis; }};void dijkstra(int u){ priority_queue
qu; memset(dis,inf,sizeof(dis)); dis[u] = 0; qu.push(node(0,u,-1)); while(!qu.empty() && (int)e.size() <= k) { int h = qu.top().to; node now = qu.top(); qu.pop(); if(vis[h]) continue; vis[h] = true; e.push_back(now.id); for(int i = head[h];i;i = edge[i].nxt) { int to = edge[i].to,val = edge[i].val; if(dis[to] > dis[h]+val) { dis[to] = dis[h]+val; qu.push(node(dis[to],to,edge[i].id)); } } }}signed main(){ n = read(),m = read(),k = read(); for(int i = 1;i <= m;i++) { int from = read(),to = read(),val = read(); addedge(from,to,val,i); addedge(to,from,val,i); } dijkstra(1); printf("%d\n",(int)e.size()-1); for(int i = 1;i < (int)e.size();i++) printf("%d ",e[i]); return 0;}

转载地址:http://ghrxz.baihongyu.com/

你可能感兴趣的文章
mysql 存储过程 注入_mysql 视图 事务 存储过程 SQL注入
查看>>
MySQL 存储过程参数:in、out、inout
查看>>
mysql 存储过程每隔一段时间执行一次
查看>>
mysql 存在update不存在insert
查看>>
Mysql 学习总结(86)—— Mysql 的 JSON 数据类型正确使用姿势
查看>>
Mysql 学习总结(87)—— Mysql 执行计划(Explain)再总结
查看>>
Mysql 学习总结(88)—— Mysql 官方为什么不推荐用雪花 id 和 uuid 做 MySQL 主键
查看>>
Mysql 学习总结(89)—— Mysql 库表容量统计
查看>>
mysql 实现主从复制/主从同步
查看>>
mysql 审核_审核MySQL数据库上的登录
查看>>
mysql 导入 sql 文件时 ERROR 1046 (3D000) no database selected 错误的解决
查看>>
mysql 导入导出大文件
查看>>
MySQL 导出数据
查看>>
mysql 将null转代为0
查看>>
mysql 常用
查看>>
MySQL 常用列类型
查看>>
mysql 常用命令
查看>>
Mysql 常见ALTER TABLE操作
查看>>
MySQL 常见的 9 种优化方法
查看>>
MySQL 常见的开放性问题
查看>>