博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeForces - 1076D Edge Deletion(最短路径树 / dijkstra+贪心)
阅读量:608 次
发布时间: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/

你可能感兴趣的文章