【BZOJ 1576】 [Usaco2009 Jan]安全路经Travel

1576: [Usaco2009 Jan]安全路经TravelTime Limit:10 SecMemory Limit:64 MBSubmit:676Solved:231[Submit][Status]Description

Input

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input

4 51 2 21 3 23 4 43 2 12 4 3输入解释:跟题中例子相同

Sample Output

336输出解释:跟题中例子相同

HINTSource

Gold

由于最短路径只有一条，所以可以求出最短路径树。

那么我们随便加入一条非树边(u,v)，就会形成一个环：

加入红边之后，蓝色点的路径会被更新。

蓝色点其实就是环上除了lca(u,v)之外的所有点，那么他们被更新成什么了？

i点：dist[u]+dist[v]+E(u,v)-dist[i]

因此更新后的答案与uv这条边的k=dist[u]+dist[v]+E(u,v)是有关的，为了求出最短的，我们只要按照每条边的k值升序排序，依次更新即可。

已经更新过的点，再遇到时就不必更新了，我是用并查集水过的。。

正解应该是树链剖分，用线段树来做即可。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>#define M 100005#include <queue>#define inf 0x3f3f3f3fusing namespace std;int h[M],d[M],now=0,tot=0,m,n,inq[M],ans[M],f[M],fa[M];struct edge{int x,y,ne,t;}e[M*5],e1[M*5];struct Edge{int x,y,v;}E[M*5];void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Addedge(int x,int y,int t){e[++tot].y=y;e[tot].ne=h[x];e[tot].t=t;h[x]=tot;}void spfa(){for (int i=1;i<=n;i++)d[i]=inf,inq[i]=0;queue<int> q;q.push(1),inq[1]=1,fa[1]=0,d[1]=0;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (d[y]>d[x]+e[i].t){d[y]=d[x]+e[i].t;fa[y]=x;if (!inq[y]) q.push(y),inq[y]=1;}}}}bool cmp(Edge a,Edge b){return a.v<b.v;}int Getfather(int x){return f[x]==0?x:f[x]=Getfather(f[x]);}void Solve(int x,int y,int v){while (Getfather(x)!=Getfather(y)){int f1=Getfather(x),f2=Getfather(y);x=f1,y=f2;if (d[x]<d[y]) swap(x,y);ans[x]=v-d[x];now++;f[x]=fa[x];x=f[x];}}int main(){read(n),read(m);for (int i=1;i<=m;i++){int x,y,t;read(x),read(y),read(t);Addedge(x,y,t),Addedge(y,x,t);e1[i].x=x,e1[i].y=y,e1[i].t=t;}spfa();tot=0;for (int i=1;i<=m;i++){int x=e1[i].x,y=e1[i].y,t=e1[i].t;if (fa[x]!=y&&fa[y]!=x){E[++tot].x=x;E[tot].y=y;E[tot].v=d[x]+d[y]+t;}}sort(E+1,E+1+tot,cmp);for (int i=1;i<=n;i++)ans[i]=-1,f[i]=0;for (int i=1;i<=tot;i++){Solve(E[i].x,E[i].y,E[i].v);if (now==n-1) break;}for (int i=2;i<=n;i++)printf("%d\n",ans[i]);return 0;}

感悟：

1.这道题的关键在于对非树边权值的转化，以及运用并查集快速往上爬

2.并查集复杂度应该是O(n)的吧？为什么会超时呢？？

UPD：

因为这道题卡SPFA!!!

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>#define M 100005#include <queue>#define inf 0x3f3f3f3fusing namespace std;struct node{int x,d;bool operator <(const node &A)const{return A.d<d;}};priority_queue<node> q;int h[M],v[M],d[M],now=0,tot=0,m,n,inq[M],ans[M],f[M],fa[M];struct edge{int x,y,ne,t;}e[M*5],e1[M*5];struct Edge{int x,y,v;}E[M*5];void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Addedge(int x,int y,int t){e[++tot].y=y;e[tot].ne=h[x];e[tot].t=t;h[x]=tot;}void spfa(){for (int i=1;i<=n;i++)d[i]=inf,inq[i]=0;queue<int> q;q.push(1),inq[1]=1,fa[1]=0,d[1]=0;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (d[y]>d[x]+e[i].t){d[y]=d[x]+e[i].t;fa[y]=x;if (!inq[y]) q.push(y),inq[y]=1;}}}}void dijkstra(){for (int i=1;i<=n;i++)v[i]=0,d[i]=inf;d[1]=0;node x;x.x=1,x.d=0;q.push(x);while (!q.empty()){x=q.top();q.pop();v[x.x]=1;for (int i=h[x.x];i;i=e[i].ne)if (!v[e[i].y]&&d[x.x]+e[i].t<d[e[i].y]){d[e[i].y]=d[x.x]+e[i].t;node r;fa[e[i].y]=x.x;r.x=e[i].y,r.d=d[e[i].y];q.push(r);}}}bool cmp(Edge a,Edge b){return a.v<b.v;}int Getfather(int x){return f[x]==0?x:f[x]=Getfather(f[x]);}void Solve(int x,int y,int v){while (Getfather(x)!=Getfather(y)){int f1=Getfather(x),f2=Getfather(y);x=f1,y=f2;if (d[x]<d[y]) swap(x,y);ans[x]=v-d[x];now++;f[x]=fa[x];x=f[x];}}int main(){read(n),read(m);for (int i=1;i<=m;i++){int x,y,t;read(x),read(y),read(t);Addedge(x,y,t),Addedge(y,x,t);e1[i].x=x,e1[i].y=y,e1[i].t=t;}dijkstra();//spfa();tot=0;for (int i=1;i<=m;i++){int x=e1[i].x,y=e1[i].y,t=e1[i].t;if (fa[x]!=y&&fa[y]!=x){E[++tot].x=x;E[tot].y=y;E[tot].v=d[x]+d[y]+t;}}sort(E+1,E+1+tot,cmp);for (int i=1;i<=n;i++)ans[i]=-1,f[i]=0;for (int i=1;i<=tot;i++){Solve(E[i].x,E[i].y,E[i].v);if (now==n-1) break;}for (int i=2;i<=n;i++)printf("%d\n",ans[i]);return 0;}改成堆优化的dijkstra之后

谢谢@cjk_cjk的提醒~

，夫妇一条心，泥土变黄金。