D. Edge Deletion

56 阅读 0 评论 37 点赞

我是靠谱客的博主单薄苗条，最近开发中收集的这篇文章主要介绍D. Edge Deletion，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

$题意：给定一张无向图，问最多保留 k 条边，使得有 1 到其余点$

$的最短路不变的点数最多。$

$分析：最短路径树，很明显，当 k \geq n - 1 时，我们只需要保$
$留最短路径上的边即可$

$当 k \leq n - 1 时，需要删除最短路径树上的一些边$

$且这些边为最深层的边$

$在跑最短路的同时利用 p r e 记录每个点的前驱，然后重新建出$

$最短路径树，最后 b f s 记录边即可$

$c o d e :$

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include<cstring>
#include <stdio.h>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl "n"
#define ll long long
#define Mp make_pair
#define INF 0x3f3f3f3f
#define Pair pair<int,int>
typedef unsigned long long ull;
#define IO ios::sync_with_stdio(false);
const int N = 2e6+5;
const int maxn = 3e5+5;
#define int long long
vector<Pair>e[maxn];
int pre[maxn];
int dis[maxn],vis[maxn];
void Dij(int s)
{
memset(dis,INF,sizeof dis);
priority_queue<Pair,vector<Pair>,greater<Pair>>q;
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue; vis[x]=true;
for(auto v:e[x])
{
int y=v.first,w=v.second;
if(dis[y]>dis[x]+w){
dis[y]=dis[x]+w;
pre[y]=x;
if(!vis[y]) q.push({dis[y],y});
}
}
}
}
int n,m,k;
bool use[maxn];
vector<int>ee[N],ans;
map<int,map<int,int>>mp,p;
void dfs(int x)
{
int y=pre[x];
if(y==-1||p[x][y]==1) return;
p[x][y]=p[y][x]=1;
ee[y].push_back(x);
dfs(y);
}
void bfs(int s)
{
int cnt=0;
queue<int>q; q.push(s);
while (!q.empty())
{
int x=q.front(); q.pop();
for(auto y:ee[x])
{
if(cnt<k&&!use[mp[x][y]])
ans.push_back(mp[x][y]),use[mp[x][y]]=true,cnt++;
if(cnt==k) break;
q.push(y);
}
if(cnt==k) break;
}
cout<<ans.size()<<endl;
for(auto id:ans) cout<<id<<" ";
cout<<endl;
}
void solve()
{
cin>>n>>m>>k;
memset(pre,-1,sizeof pre);
k=min(k,n-1);
for(int i=1;i<=m;i++){
int u,v,w; cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
mp[u][v]=i;
mp[v][u]=i;
}
Dij(1);
for(int i=1;i<=n;i++) dfs(i);
bfs(1);
}
signed main()
{
//
freopen("5.in","r",stdin);
//
freopen("5.out","w",stdout);
IO;
//
int T;cin>>T; while (T--)
solve();
return 0;
}