题目描述
给定一个由 n 个点和 m 条边组成的无向连通加权图。
设点 1 到点 i 的最短路径长度为 di。
现在,你需要删掉图中的一些边,使得图中最多保留 k 条边。
如果在删边操作全部完成后,点 1 到点 i 的最短路径长度仍为 di,则称点 i 是一个优秀点。
你的目标是通过合理进行删边操作,使得优秀点的数量尽可能大。
算法
重要结论:1到每个点最短路径构成的链的并集可以为一棵树
证明:
为了保留尽量少的边,当最短路路径有多种可能时,我们设1->u的最短路每次都走同一条
即如果1->v最短路径经过u,那么1->v中1->u的路径和1->u的最短路路径相同
这样就不可能有环了
d[v]-d[u]==e[i].c判断u->v是否在最短路树上
每个v只能被第一个找到它的u更新,保证树形结构
时间复杂度
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,m,k;
struct Node{
int v,c,nxt,id;
}e[N<<1];
int tot,h[N];
void addEdge(int u,int v,int c,int id)
{
tot++;
e[tot].v=v;e[tot].c=c;e[tot].nxt=h[u];h[u]=tot;
e[tot].id=id;
}
struct Point{
int x;
LL y;
bool operator <(const Point &t)const
{
return y>t.y;
}
};
priority_queue<Point>q;
LL d[N];
bool used[N];
void dijk()
{
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push({1,0});
while(!q.empty())
{
int u=q.top().x;
q.pop();
if(used[u])
{
continue;
}
used[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].c)
{
d[v]=d[u]+e[i].c;
q.push({v,d[v]});
}
}
}
}
int vis[N],ans[N];
int main()
{
int u,v,c;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c,i);
addEdge(v,u,c,i);
}
dijk();
int q[N];
int hh=1,tt=0;
q[++tt]=1;vis[1]=1;
while(hh<=tt)
{
u=q[hh];
for(int i=h[u];i;i=e[i].nxt)
{
v=e[i].v;
if(vis[v])
{
continue;
}
if(d[v]-d[u]==e[i].c)
{
q[++tt]=v;
vis[v]=1;
ans[++ans[0]]=e[i].id;
}
}
hh++;
}
ans[0]=min(ans[0],k);
printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];i++)
{
printf("%d ",ans[i]);
}
return 0;
}