CF1076D Edge Deletion 最短路树

问题描述

Codeforces

洛谷（有翻译）

题解

最短路树，是一棵在最短路过程中构建的树。

在\(\mathrm{Dijkstra}\)过程中，如果最终点\(y\)是由点\(x\)转移得到的，则在最短路树上\(x\)是\(y\)的父节点，\(x\)到\(y\)的最短路树上长度等于原图上转移\(x,y\)的边的长度。

显然每一条边最多能贡献\(1\)的答案。

在最短路树上选取边，能保证每一条边都贡献答案。

选取的边连接的点和根结点\(1\)要是联通块。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long
//三年OI一场空，不开long long见祖宗

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=300000+7;
const int maxm=600000+7;

int Head[maxn],to[maxm],Next[maxm],tot=1,w[maxm];
int n,m,k;
int dis[maxn];

void add(int x,int y,int z){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
}

struct node{
    int dis,id;
    bool operator <(const node &a)const
    {
        return dis>a.dis;
    } 
};

bool vis[maxn];

void dijkstra(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;priority_queue<node>q;
    q.push((node){0,st});
    while(!q.empty()){
        int x=q.top().id;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(dis[y]>dis[x]+w[i]){
                dis[y]=dis[x]+w[i];q.push((node){dis[y],y});
            }
        }
    }
}

bool ins[maxn];

void dfs(int x){
    ins[x]=1;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(!ins[y]&&dis[y]==dis[x]+w[i]){
            printf("%I64d ",(i>>1));
            --k;if(!k) exit(0);
            dfs(y);
        }
    }
}

signed main(){
    read(n);read(m);read(k);
    printf("%I64d\n",min(n-1,k));
    if(!k) return 0;
    for(int xx,yy,zz,i=1;i<=m;i++){
        read(xx);read(yy);read(zz);add(xx,yy,zz);add(yy,xx,zz);
    }
    dijkstra(1);dfs(1);
    return 0;
}