P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

· · 题解

题目传送门

思路：

这道题问最多有多少条路径并且这些路径长度和要小于等于 e，我们可以先到贪心前 k 短路，k 就是答案。

介于它增加了数据使得我不得不使用可持久化合并堆对它进行优化。

我们对于反图跑一边最短路，其中 dis_i 表示从点 i 到点 n 的最短路，接着建一棵最短路树 G。对于每条非树边 e，它会给原来的路径加上 dist_v + w - dist_u，u \text{ 和 } v 是边的两个端点，w 是边的长度。我们把这个值当做是这条边是新的权值推到左偏树中。

我们用小根堆来维护这些非树边，每次取出权值最小的边。当前取出的边的起点是点 u。那么我们有两种转换方式。

  1. 在小根堆中加一个一 个 u 为起点并且权值大于等于取出来边的权值的边。

  2. 在小跟堆中加入一个这条边结尾的节点在左偏树中祖先连的非树边。

AC code

#include <bits/stdc++.h>
using namespace std;
#define pii pair<double,int>
const double ep = 1e-8;
const int N = 10005;
const int M = 200005;
int n,m;
double E;
struct node{
    int id,v;
    double w;
};
vector<node>road[N],rroad[N];
double dist[N];
int root[N];
namespace LT{
    struct point{
        int lson,rson,last;
        int dist;
        double val;
    }tr[M * 20];
    int cnt = 0;
    int create(double v,int last)
    {
        int u = ++cnt;
        tr[u].val = v;
        tr[u].last = last;
        tr[u].dist = tr[u].lson = tr[u].rson = 0;
        return cnt;
    }
    int cop(int id)
    {
        int u = ++cnt;
        tr[u] = tr[id];
        return u;
    }
    int merge(int x,int y)
    {
        if(x == 0 || y == 0)
        {
            return x | y;
        }
        if(tr[x].val > tr[y].val)
        {
            swap(x,y);
        }
        int u = cop(x);
        tr[u].rson = merge(tr[u].rson,y);
        if(tr[tr[u].lson].dist < tr[tr[u].rson].dist)
        {
            swap(tr[u].lson,tr[u].rson);
        }
        tr[u].dist = tr[tr[u].rson].dist + 1;
        return u;
    }
    void insert(int &rt,double val,int last)
    {
        rt = merge(create(val,last),rt);
    }
}
using namespace LT;
priority_queue<pii,vector<pii>,greater<pii> >q;
void dij()
{
    for(int i = 0;i < N;i++)
    {
        dist[i] = 1e9;
    }
    dist[n] = 0;
    q.push((pii){0.0,n});
    while(!q.empty())
    {
        int u = q.top().second;
        double len = q.top().first;
        q.pop();
        if(dist[u] != len)
        {
            continue;
        }
        for(int i = 0;i < rroad[u].size();i++)
        {
            int v = rroad[u][i].v;
            double l = rroad[u][i].w;
            if(dist[v] > dist[u] + l)
            {
                dist[v] = dist[u]+ l;
                q.push((pii){dist[v],v});
            }
        }
    }
}
int f[N];
int st[N];
bool vis[N];
int top;
bool line[M];//当前边是不是树边
void dfs(int u)
{
    st[++top] = u;
    vis[u] = true;
    for(int i = 0;i < rroad[u].size();i++)
    {
        int v = rroad[u][i].v;
        double l = rroad[u][i].w;
        if(dist[v] == dist[u] + l && vis[v] == false)
        {
            line[rroad[u][i].id] = true;
            f[v] = u;
            dfs(v);
        }
    }
}
void build()
{
    for(int i = 1;i<=top;i++)
    {
        int u = st[i];
        root[u] = root[f[u]];
        for(int i = 0;i < road[u].size();i++)
        {
            int id = road[u][i].id;
            int v = road[u][i].v;
            double w = road[u][i].w;
            if(!line[id] && dist[v] != dist[0])
            {
                insert(root[u],dist[v] + w - dist[u],v);
            }
        }
    }
}
int kshort()
{
    int cnt = 1;
    E-=dist[1];
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push((pii){dist[1] + tr[root[1]].val,root[1]});
    while(!q.empty())
    {
        double len = q.top().first;
        int u = q.top().second;
        q.pop();
        if(len -ep>E)break;
        E-=len - ep;
        cnt++;
        int l = tr[u].lson;
        int r = tr[u].rson;
        int top = tr[u].last;
        if(root[top])
        {
            q.push((pii){len + tr[root[top]].val,root[top]});
        }
        if(l)
        {
            q.push((pii){len + tr[l].val - tr[u].val,l});
        }
        if(r)
        {
            q.push((pii){len + tr[r].val - tr[u].val,r});
        }
    }
    return cnt;
}
int main()
{
    scanf("%d%d%lf",&n,&m,&E);
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        double w;
        scanf("%d%d%lf",&u,&v,&w);
        if(u == n)//特判u为n的路
        {
            i--;
            m--;
            continue;
        }
        road[u].push_back((node){i,v,w});
        rroad[v].push_back((node){i,u,w});//建反图
    }
    dij();//反图跑最短路
    dfs(n);//建最短路树
    build();//建左偏树
    printf("%d\n",kshort());
    return 0;
}