[SDOI2010]魔法猪学院

[SDOI2010]魔法猪学院

一、题目

点此看题

二、解法

直接讲人话把，网上的什么性质和结论看得我想吐。

首先建出以 t t t为根的最短路树，在反图上跑最短路然后建树，多条满足条件的边任选即可。

我们考虑用非树边替换树边，定义一条边 ( u , v ) (u,v) (u,v)的权值是 c − d i s [ u ] + d i s [ v ] c-dis[u]+dis[v] c−dis[u]+dis[v] （ d i s dis dis为树上的到根的距离， c c c是壁边权），实际意义就是选择这条边多出来的距离，显然任意权值都是非负的。从 1 1 1开始跑一个优先队列，选择某一个祖先（或自身）最小权值，优先队列有两种扩展方式，第一种是用当前的次小权值替换最小权值，第二种是跑到最小权值边链接的地方选择那里的最小权值开始跑，这样就会一直扩展到 k k k短路了。

分析上面的问题，不难发现我们要使用堆，但是我们需要的祖先（或自身）的最小权值，就需要从祖先一路合并下来，故要用左偏树，祖先和自身的权值都可能被用到，我们不能改变左偏树的结构，所以要用可持久化左偏树。其实可持久化左偏树的思路很简单，在合并的时候不修改 x x x的右儿子而是直接新建节点，这样就保证的树的形态不变。

时间复杂度 & & &空间复杂度 O ( m log ⁡ m ) O(mlog m) O(mlogm)，贴个代码 q w q qwq qwq。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define eps 1e-8
const int M = 200005;
int read()
{int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*flag;
}
int n,m,tot,cnt,ans,f[M],vis[M],rt[M],cov[2*M],fa[M];
double s,c,dis[M];
struct edge
{int v;double c;int next;
}e[2*M];
struct data
{int ls,rs,dis,ed;double v;
}t[20*M];
struct node
{double a;int b;bool operator < (const node &B) const{return a>B.a;}
};priority_queue<node> q;
double Abs(double x)
{return x>0?x:-x;
}
void dfs(int u)
{vis[u]=1;for(int i=f[u];i;i=e[i].next)if(i&1){c=e[i].c;int v=e[i].v;if(Abs(dis[u]+c-dis[v])<eps && !vis[v])fa[v]=u,cov[i^1]=1,dfs(v);}
}
int merge(int x,int y)
{if(!x || !y) return x+y;if(t[x].v-t[y].v>=eps) swap(x,y);int p=++cnt;t[p]=t[x];t[p].rs=merge(t[p].rs,y);if(t[t[p].ls].dis<t[t[p].rs].dis) swap(t[p].ls,t[p].rs);t[p].dis=t[t[p].rs].dis+1;return p;
}
signed main()
{t[0].dis=-1;tot++;n=read();m=read();scanf("%lf",&s);for(int i=0;i<=n;i++)dis[i]=(1ll<<40);for(int i=1;i<=m;i++){int u=read(),v=read();scanf("%lf",&c);e[++tot]=edge{v,c,f[u]},f[u]=tot;e[++tot]=edge{u,c,f[v]},f[v]=tot;}dis[n]=0;q.push(node{0,n});while(!q.empty()){int u&#p().b;q.pop();if(vis[u]) continue;vis[u]=1;for(int i=f[u];i;i=e[i].next)if(i&1){int v=e[i].v;c=e[i].c;if(dis[v]-(dis[u]+c)>=eps)q.push(node{dis[v]=dis[u]+c,v});}}for(int i=1;i<=n;i++) vis[i]=0;dfs(n);for(int i=2;i<tot;i+=2)if(!cov[i]){int u=e[i^1].v,v=e[i].v;if(dis[u]==dis[0] || dis[v]==dis[0]) continue;t[++cnt].ed=v;t[cnt].v=dis[v]-dis[u]+e[i].c;rt[u]=merge(rt[u],cnt);}for(int i=1;i<=n;i++) q.push(node{dis[i],i});for(int i=1;i<=n;i++){int u&#p().b;q.pop();rt[u]=merge(rt[u],rt[fa[u]]);}s-=dis[1];ans++;if(rt[1]) q.push(node{t[rt[1]].v,rt[1]});while(!q.empty()){int x&#p().b;c&#p().a;if(dis[1]+c-s>=eps) break;q.pop();ans++;s-=dis[1]+c;for(int i=0;i<2;i++){int to=i?t[x].rs:t[x].ls;if(to) q.push(node{c-t[x].v+t[to].v,to});}if(rt[t[x].ed]) q.push(node{t[rt[t[x].ed]].v+c,rt[t[x].ed]});}printf("%dn",ans);
}