题解 CF1076D 【Edge Deletion】
Hexarhy
2021-05-14 22:06:50
### Preface
最短路径树 SPT 练习题，难度相当于模板。
### Solution
读题发现有删边后最短路不变的性质，暗示我们求 SPT，于是我们把这个 SPT 建出来。
SPT 上每个点到节点 $1$ 都是最短路径，经过的边都是对最短路有贡献的，剩下的边都可以删。因此 SPT 上的边便是最优方案。
同时，从节点 $1$ 出发，对这个 SPT 遍历 $\min\{k,n-1\}$ 条边，记录边的编号输出即可。这样也能保证图的连通。
### Code
```cpp
// Problem: CF1076D Edge Deletion
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1076D
// Memory Limit: 250 MB
// Time Limit: 2500 ms
// Author: Hexarhy
//
// Powered by CP Editor (https://cpeditor.org)
typedef long long ll;//开 ll
typedef const int cint;
cint MAXN=3e5+5;
int n,m,k,sum;
struct node
{
int to;ll val;int id;
bool operator<(const node& a)const
{
return val>a.val;
}
};
vector<node> edge[MAXN];
vector<int> ans;
struct Edge
{
int u,v;ll w;
}e[MAXN];
ll dis[MAXN];
int pre[MAXN];
bool visit[MAXN];
void dijkstra(void)
{
priority_queue<node> q;
for(int i=1;i<=n;i++) dis[i]=LLONG_MAX;
dis[1]=0;
q.emplace(node{1,0,0});
while(!q.empty())
{
cint u=q.top().to;q.pop();
if(visit[u]) continue;
visit[u]=true;
for(const auto& it:edge[u])
{
cint v=it.to,w=it.val,id=it.id;
if(dis[v]>=dis[u]+w)
{
if(dis[v]>dis[u]+w || e[pre[v]].w>w) pre[v]=id;//习惯了求最小最短路径树 MSPT
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.emplace(node{v,dis[v],0});
}
}
}
}
}
void dfs(cint cur,cint fa)
{
if(sum>=k) return;
visit[cur]=true;
for(const auto& it:edge[cur])
{
cint v=it.to,id=it.id;
if(visit[v]) continue;
if(pre[v]==id)
{
ans.emplace_back(id);
++sum;
dfs(v,cur);
if(sum>=k) return;//注意回溯时要判断是否已经达到 k
}
}
}
int main()
{
read(n,m,k);
for(int i=1;i<=m;i++)
{
int u,v;ll w;read(u,v,w);
e[i]=Edge{u,v,w};
edge[u].emplace_back(node{v,w,i});
edge[v].emplace_back(node{u,w,i});
}
dijkstra();
memset(visit,false,sizeof(visit));
dfs(1,0);
cout<<min(n-1,k)<<endl;
for(const auto& Ans:ans) cout<<Ans<<' ';
return 0;
}
```