【Codeforces 1076D】Edge Deletion | 最短路树

48 阅读 0 评论 32 点赞

我是靠谱客的博主还单身鸭子，最近开发中收集的这篇文章主要介绍【Codeforces 1076D】Edge Deletion | 最短路树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

给定n,m,k：n个点,m条边，要进行删边操作，最后可以保留最多k条边

定义一个点i是好的当且仅当在删除一些边之后，1->i的最短路等于未删边之前的最短路

输出最多可以有多少个好的点，输出保留边的个数与保留边的编号

题目思路：

刚开始看到删边，联想到最短路径还原。

考虑求最短路的过程，可以知道求最短路的过程中一定会存在没有用的一些边即对最短路根本没有影响的边。

如果对于一条边来说满足：dis[s]+w = = dis[e] ，那么s这条边在1 -> e的最短路上

所以首先把不满足这个条件的边删掉

之后考虑剩下的边，显然可见最短路是分层的：

此时，显而易见肯定从后向前删，因为删除过程中的一下子会失去大于等于1个点，而删最后只会失去一个点。

考虑一下拓扑排序或许可以解决这个问题。

但是呢考虑这个边权都是正数，起点又固定，所以最短路按分层来说绝对是距离越来越大，所以只需要排序，保留前k个点即可

wa7..

又随便考虑一下这个问题，发现有一种情况:

基于上面的图，或许会还原出这种情况:

此时删除点4以为删除2条边，所以可能会出错。

所以去重一下，每一个点只对应一条边，现在来说就可以一个点对应一个权值，然后排序之后保留前k个点，也就保留了前k条边。

注意：

1.这个题因为是d2的，所以绝对有不法份子专门卡spfa【赛时hack机制】，所以建议优化的最短路

2.亲测最短路的值爆了long long

Code：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e17;
const int maxn=1e6+6;
const int mod=998244353;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct node{
    int s,e,next;
    ll w;
}edge[maxn];
ll cnt = 0;
int head[maxn];
void addedge(int u,int v,ll w){
    edge[cnt]=node{u,v,head[u],w};
    head[u]=cnt++;
}
ll dis[maxn];
struct N{
    int id;
    ll w;
    bool friend operator<(N a,N b)
    {
        return a.w>b.w;
    }
};
void dijstra(int st)
{
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[st]=0;
    N s;s.id=st;s.w=0;
    priority_queue<N>q;
    q.push(s);
    while(!q.empty())
    {
        N u=q.top();q.pop();
        if(dis[u.id]!=u.w) continue;
        for(int i=head[u.id];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>u.w+edge[i].w)
            {
                dis[e]=u.w+edge[i].w;
                N now;now.id=e;
                now.w=dis[e];
                q.push(now);
            }
        }
    }
}
pair<ll,int>save[maxn];
int visp[maxn];
ll res=0;
void rebuild(){
    for(int i=0;i<cnt;i++)
        if(dis[edge[i].s]+edge[i].w==dis[edge[i].e]&&!visp[edge[i].e]){
            save[++res]={dis[edge[i].e],i/2+1};
            visp[edge[i].e]=1;
        }
}
int main(){
    memset(head,-1,sizeof(head));
    read(n);read(m);read(p);
    for(int i=1;i<=m;i++){
        int x,y;ll w;
        scanf("%d%d%lld",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
    }
    dijstra(1);
    rebuild();
    if(p>=res){
        printf("%lldn",res);
        for(int i=1;i<=res;i++)
            printf("%d ",save[i].second);
    }
    else{
        printf("%lldn",p);
        sort(save+1,save+1+res);
        for(int i=1;i<=p;i++)
            printf("%d ",save[i].second);
    }
    printf("n");
    return 0;
}
/**
4 5 3
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5

**/