SDOI2010 魔法猪学院

SDOI2010 魔法猪学院

题目描述

题解：

明显的$k$短路问题，这里提供两种方法。

1.$A$*算法

$A$*可以解决一般的$k$短路问题，但是并不如可持久化可并堆优秀。

$A$*的本质是$f+g$，而估价函数可以用终止节点到终点的最短路表示。

所以先反向建图$dij$，然后小根堆跑$A$*即可。

优化一下，总代价/起点终点最短路就是每个点经过的最大次数。

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5050;
const int M = 200050;
const double eps = 1e-8;
template<typename T>
inline void read(T&x)
{T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c;
}
int n,m,hed[N],cnt,heb[N],cnb;
double lim;
struct EG
{int to,nxt;double w;
}e[2*M],br[2*M];
void ae(int f,int t,double w)
{e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;hed[f] = cnt;
}
void ab(int f,int t,double w)
{br[++cnb].to = t;br[cnb].nxt = heb[f];br[cnb].w = w;heb[f] = cnb;
}
double g[N];
bool vis[N];
struct Pair
{int x;double d;Pair(){}Pair(int x,double d):x(x),d(d){}friend bool operator < (Pair a,Pair b){return a.d>b.d;}
}tp;
void dij()
{priority_queue<Pair>q;for(int i=1;i<n;i++)g[i]=1e18;q.push(Pair(n,0.0));while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(vis[u])continue;vis[u] = 1;for(int j=heb[u];j;j=br[j].nxt){int to = br[j].to;if(g[to]-g[u]-br[j].w>eps){g[to] = g[u]+br[j].w;q.push(Pair(to,g[to]));}}}
}
int ans,t[N];
void A_star()
{priority_queue<Pair>q;q.push(Pair(1,g[1]));int kk = (int)(lim/g[1])+1;while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(lim-tp.d+eps<0)break;if(u==n){lim-=tp.d;ans++;continue;}t[u]++;if(t[u]>kk)continue;for(int j=hed[u];j;j=e[j].nxt){int to = e[j].to;if(lim-(tp.d-g[u]+e[j].w+g[to])+eps>0){q.push(Pair(to,tp.d-g[u]+e[j].w+g[to]));}}}
}
int main()
{read(n),read(m);scanf("%lf",&lim);if(lim>1000000){puts("2002000");return 0;}int f,t;double w;for(int i=1;i<=m;i++){read(f),read(t);scanf("%lf",&w);ae(f,t,w);ab(t,f,w);}dij();A_star();printf("%dn",ans);return 0;
}

2.可持久化可并堆

这绝壁是个柯学做法。

先放大牛$pdf$。

先建出最短路树。

对于每条非树边，我们都能得到经过这条边至少多绕多远。

对于一种绕远方案，方案总长=起点终点最短路+多绕的距离。

由于一个点沿最短路树边向终点移动时并不会绕远，所以它可以自由“向上”移动。

所以先对于每个点处理从该点出发的非树边，将其放入小根堆中，

然后$dfs$/按拓扑序从树根到叶节点合并小根堆。

最后用一个小根堆维护就好了。

代码：

/**************************************************************Problem: 1975User: LiGuanlinLanguage: C++Result: AcceptedTime:600 msMemory:56784 kb
****************************************************************/#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5050;
const int M = 200050;
const int MAXN = 10*M;
const double eps = 1e-8;
template<typename T>
inline void read(T&x)
{T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c;
}
int n,m,fa[N],tot,rt[N],pre[N];
double lim,g[N];
bool vis[N];
struct node
{int ls,rs,dis,tl;double v;
}p[MAXN];
int merge(int x,int y)
{if(!x||!y)return x+y;if(p[x].v-p[y].v>=eps)swap(x,y);int u = ++tot;p[u] = p[x];p[u].rs = merge(p[u].rs,y);if(p[p[u].ls].dis<p[p[u].rs].dis)swap(p[u].ls,p[u].rs);p[u].dis = p[p[u].rs].dis+1;return u;
}
struct Pair
{int x;double d;Pair(){}Pair(int x,double d):x(x),d(d){}friend bool operator < (Pair a,Pair b){return a.d>b.d;}
}tp;
int hed[N],cnt=1;
bool cov[2*M];
struct EG
{int to,nxt;double w;
}e[2*M];
void ae(int f,int t,double w)
{e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;hed[f] = cnt;
}
void dij()
{priority_queue<Pair>q;for(int i=1;i<n;i++)g[i]=1e18;q.push(Pair(n,0.0));while(!q.empty()){tp = q.top();q.pop();int u = tp.x;if(vis[u])continue;vis[u] = 1;for(int j=hed[u];j;j=e[j].nxt){if(j&1){int to = e[j].to;if(g[to]+eps>g[u]+e[j].w){g[to] = g[u]+e[j].w;q.push(Pair(to,g[to]));}}}}
}
void dfs(int u)
{vis[u] = 1;for(int j=hed[u];j;j=e[j].nxt)if(j&1){int to = e[j].to;if(fabs(g[to]-(e[j].w+g[u]))<=eps&&!vis[to]){fa[to] = u;cov[j^1] = 1;dfs(to);}}
}
void topo()
{priority_queue<Pair>q;for(int i=1;i<=n;i++)q.push(Pair(i,g[i]));for(int u,i=1;i<=n;i++){u = q.top().x;q.pop();if(fa[u])rt[u] = merge(rt[u],rt[fa[u]]);}
}
int main()
{read(n),read(m);scanf("%lf",&lim);int f,t;double w;for(int i=1;i<=m;i++){read(f),read(t);scanf("%lf",&w);ae(f,t,w);ae(t,f,w);}dij();memset(vis,0,sizeof(vis));dfs(n);for(int j=2;j<=cnt;j+=2){if(!cov[j]){int f = e[j^1].to,t = e[j].to;double w = g[t]+e[j].w-g[f];p[++tot].v = w,p[tot].dis = 1,p[tot].tl = t;rt[f] = merge(rt[f],tot);}}topo();priority_queue<Pair>q;int ans = 0;if(lim+eps>g[1])lim-=g[1],ans++;if(rt[1])q.push(Pair(rt[1],p[rt[1]].v));while(!q.empty()){tp = q.top();q.pop();if(lim+eps>tp.d+g[1])lim-=(tp.d+g[1]),ans++;else break;int u = tp.x,ls = p[u].ls,rs = p[u].rs;if(ls)q.push(Pair(ls,tp.d-p[u].v+p[ls].v));if(rs)q.push(Pair(rs,tp.d-p[u].v+p[rs].v));int t = p[u].tl;if(rt[t])q.push(Pair(rt[t],p[rt[t]].v+tp.d));}printf("%dn",ans);return 0;
}

转载于:.html