精华内容
参与话题
问答
  • 最短路径树

    千次阅读 2016-07-17 17:14:13
    【问题描述】 所谓最短路径树,就是从s出发,沿着树上的边走到任意点i,那么经过的这些边的权值和就是s到i的最短路径。Dijkstra算法或SPFA算法不仅可计算从起点s到各点的最短路径长度,同时也可得到以s为根的最短...

    【问题描述】

      所谓最短路径树,就是从s出发,沿着树上的边走到任意点i,那么经过的这些边的权值和就是s到i的最短路径。Dijkstra算法或SPFA算法不仅可计算从起点s到各点的最短路径长度,同时也可得到以s为根的最短路径树。方法是在进行松弛操作时,如果d[i] + c < d[j] 时,除了更新d[j]之外,还要设置fa[j]=i。这样把fa[j]看成j的父亲指针,则所有点形成了一棵树(因为每个结点都有唯一的前驱)。这样要从起点s出发沿最短路走到任意点,只需要顺着树边走即可。

      现在请你利用最短路径树解下面这个决问题:
      n个城市用m条双向公路连接,使得任意两个城市都能直接或间接地连通。其中城市编号为1..n,公路编号为1..m。任意个两个城市间的货物运输会选择最短路径,把这n*(n-1)条最短路径的和记为S。
      现在你来寻找关键公路r,公路r必须满足:当r堵塞之后,S的值会变大(如果r堵塞后使得城市u和v不可达,则S为无穷大)。

    【输入格式】

      第1行包含两个整数n,m,接下来的m行,每行用三个整数描述一条公路a,b,len(1<=a,b<=n),表示城市a和城市b之间的公路长度为len,这些公路依次编号为1..m。

    【输出格式】

      从小到大输出关键公路的编号。

    【输入样例】

    4 6
    1 2 1
    2 3 1
    3 4 1
    1 4 1
    1 3 1
    4 1 1

    【输出样例】

    1
    2
    3
    5

    【数据范围】

    对于20%的数据,有n<=50,1<=m<=1000。
    对于100%的数据,有n<=100,1<=m<=3000,1<=len<=10000。

    此题需要一每个点为起点生成一个最短路径树,再在树上枚举每条边,看是否是重要边。

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<cstdlib>
    #include<queue>
    using namespace std;
    const int maxn=105;
    const int maxm=3005;
    const int inf=200000000;
    struct shu
    {
        int u,id;
    };
    vector<int>g[maxn],w[maxn],idn[maxn];
    int n,m,d[maxn],fa[maxn],vis[maxn]={0},q[maxn*maxn];
    bool mark[maxm]={0};
    
    void init()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            g[x].push_back(y);
            w[x].push_back(z);
            idn[x].push_back(i);
            g[y].push_back(x);
            w[y].push_back(z);
            idn[y].push_back(i);
        }
    }
    
    void in()
    {
        for(int i=1;i<=n;i++)
        d[i]=inf;
    }
    
    void spfa1(int x)
    {
        int front=0,root=0;
        q[root++]=x;
        vis[x]=1;
        d[x]=0;
        while(front!=root)
        {
            int i=q[front++];
            vis[i]=0;
            for(int k=0;k<g[i].size();k++)
            {
                int j=g[i][k],c=w[i][k],z=idn[i][k];
                if(d[i]+c>=d[j]) continue;
                d[j]=d[i]+c;
                fa[j]=z;
                if(vis[j]) continue;
                q[root++]=j;
                vis[j]=1;
            }
        }
    }
    
    void spfa2(int x,int y)
    {
        int front=0,root=0;
        q[root++]=x;
        vis[x]=1;
        d[x]=0;
        while(front!=root)
        {
            int i=q[front++];
            vis[i]=0;
            for(int k=0;k<g[i].size();k++)
            {
                int j=g[i][k],c=w[i][k],z=idn[i][k];
                if(d[i]+c>=d[j]) continue;
                if(z==y) continue;
                d[j]=d[i]+c;
                if(vis[j]) continue;
                q[root++]=j;
                vis[j]=1;
            }
        }
    }
    int main()
    {
        init();
        for(int i=1;i<=n;i++)//枚举起点。
        {
            in();
            fa[i]=0;
            spfa1(i);
            int s=0;
            for(int j=1;j<=n;j++)
            s+=d[j];
            for(int j=1;j<=n;j++)//枚举边。
            if(fa[j]&&!mark[fa[j]])
            {
                in();
                spfa2(i,fa[j]);
                int ss=0;
                for(int k=1;k<=n;k++)
                  ss+=d[k];
                if(ss>s) mark[fa[j]]=1;//标记重要边。
            }
        }
        for(int i=1;i<=m;i++)
        if(mark[i])
        printf("%d\n",i);
        return 0;
    }
    展开全文
  •  BZOJ4016最短路径树问题 分析:  大家都说这是一道强行拼出来的题,属于是两种算法的模板题。  我们用dijkstra算法算出1为源点的最短路数组,然后遍历一下建出最短路树。  之后就是裸的点分治算法,一个...

    题目:

      BZOJ4016最短路径树问题

     

    分析:

      大家都说这是一道强行拼出来的题,属于是两种算法的模板题。

      我们用dijkstra算法算出1为源点的最短路数组,然后遍历一下建出最短路树。

      之后就是裸的点分治算法,一个桶,两个变量就解决了这道题。

    代码:

     1 #include<bits/stdc++.h>
     2 #define pi pair<int,int>
     3 #define pq priority_queue
     4 #define mp(a,b) make_pair(a,b)
     5 #define ms(a,x) memset(a,x,sizeof(a))
     6 using namespace std;
     7 const int N=30005;
     8 vector< pi >g[N];
     9 struct node{int y,z,nxt;}e[N*4];
    10 int n,m,k,h[N],c=0,dis[N],vis[N],nm[N];
    11 int ans2,md,rt,sm,siz[N],s[N],ans,f[N];
    12 pq< pi,vector< pi >,greater< pi > >q;
    13 void add(int x,int y,int z){
    14     e[++c]=(node){y,z,h[x]};h[x]=c;
    15     e[++c]=(node){x,z,h[y]};h[y]=c;
    16 } void dij(){
    17     ms(vis,0);ms(dis,0x3f);
    18     dis[1]=0;q.push(mp(0,1));
    19     while(!q.empty()){
    20         int x=q.top().second;q.pop();
    21         if(vis[x]) continue;vis[x]=1;
    22         for(int i=0;i<g[x].size();i++){
    23             int y=g[x][i].first,
    24             d=g[x][i].second;
    25             if(dis[y]>dis[x]+d) dis[y]=dis[x]+d,
    26             q.push(mp(dis[y],y));
    27         }
    28     } return ;
    29 } void rebuild(int x){
    30     vis[x]=1;
    31     for(int i=0;i<g[x].size();i++){
    32         int y=g[x][i].first,d=g[x][i].second;
    33         if(vis[y]||dis[x]+d!=dis[y]) continue;
    34         add(x,y,d);rebuild(y);
    35     } return ;
    36 } void getrt(int x,int fa){
    37     siz[x]=1;f[x]=0;
    38     for(int i=h[x],y;i;i=e[i].nxt)
    39     if(!vis[y=e[i].y]&&y!=fa) getrt(y,x),
    40     siz[x]+=siz[y],f[x]=max(f[x],siz[y]);
    41     f[x]=max(f[x],sm-siz[x]);
    42     if(f[rt]>f[x]) rt=x;return ;
    43 } void dfs(int x,int fa,int nw){
    44     md=max(md,nw);
    45     if(nw==k-1){
    46         if(ans==dis[x]) ans2++;
    47         if(dis[x]>ans) ans2=1,
    48         ans=dis[x];return ;
    49     } int nans=-1;
    50     if(s[k-1-nw]!=-1) nans=dis[x]+s[k-1-nw];
    51     if(ans==nans) ans2+=nm[k-1-nw];
    52     if(nans>ans) ans2=nm[k-1-nw],ans=nans;
    53     for(int i=h[x],y;i;i=e[i].nxt)
    54     if(!vis[y=e[i].y]&&y!=fa) 
    55     dis[y]=dis[x]+e[i].z,dfs(y,x,nw+1);
    56 } void update(int x,int fa,int nw){
    57     if(nw==k-1) return ;
    58     if(s[nw]==dis[x]) nm[nw]++;
    59     else s[nw]=max(s[nw],dis[x]),nm[nw]=1;
    60     for(int i=h[x],y;i;i=e[i].nxt)
    61     if(!vis[y=e[i].y]&&y!=fa) update(y,x,nw+1);
    62 } void solve(int x){
    63     md=0;vis[x]=1;
    64     for(int i=h[x],y;i;i=e[i].nxt)
    65     if(!vis[y=e[i].y]) dis[y]=e[i].z,
    66     dfs(y,x,1),update(y,x,1);
    67     for(int i=1;i<=md;i++) s[i]=-1,nm[i]=0;
    68     for(int i=h[x],y;i;i=e[i].nxt)
    69     if(!vis[y=e[i].y]) sm=siz[y],rt=0,
    70     getrt(y,x),solve(rt);
    71 } int main(){
    72     f[0]=0x3f3f3f3f;scanf("%d%d%d",&n,&m,&k);
    73     for(int i=1,x,y,z;i<=m;i++){
    74         scanf("%d%d%d",&x,&y,&z);
    75         g[x].push_back(mp(y,z));
    76         g[y].push_back(mp(x,z));
    77     } for(int i=1;i<=n;i++)
    78     sort(g[i].begin(),g[i].end());
    79     dij();ms(vis,0);rebuild(1);
    80     sm=n;rt=0;ms(vis,0);
    81     ms(dis,0);ms(s,-1);
    82     getrt(1,0);solve(rt);
    83     printf("%d %d\n",ans,ans2);
    84     return 0;
    85 }
    最短路树+点分治

     

    转载于:https://www.cnblogs.com/Alan-Luo/p/10446373.html

    展开全文
  • 首先介绍这三个概念,很多人都听过最短路径了,但是最短路径树却很少听过,关于最短路径树的介绍也不太多。而最短路径树和最小生成树更是完全不同的两个概念。 最短路径就是从一个指定的顶点出发,计算从该顶点出发...

           首先介绍这三个概念,很多人都听过最短路径了,但是最短路径树却很少听过,关于最短路径树的介绍也不太多。而最短路径树和最小生成树更是完全不同的两个概念。

           最短路径就是从一个指定的顶点出发,计算从该顶点出发到其他所有顶点的最短路径。通常用Dijkstra算法,Floyd算法求解。

           最短路径树SPT(Short Path Tree)是网络的源点到所有结点的最短路径构成的树。

           最小生成树是用和最少的边集将一个图连成任意2点可达,并且这个边集的总长度最小。保证整个拓扑图的所有路径之和最小。通常用Prim算法和kruskal算法求解。

           下面是最短路径树和最小生成树的对比图,原图来论文[1]。

    原图:


    对比图:

                               最短路径树图                                    最小生成树图   

            最短路径树的路径总长度为75,最小生成树的路径总长度为67.


    [1]杨晓花,武继刚,史雯隽,赵国栋,稳定的最短路径树及其构造算法[J],计算机工程与科学,2016,38(3):418-424.

    展开全文
  • 【BZOJ4016】[FJOI2014]最短路径树问题 Description 给一个包含n个点,m条边的无向连通图。从顶点1出发,往其余所有点分别走一次并返回。 往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则...

    【BZOJ4016】[FJOI2014]最短路径树问题

    Description

    给一个包含n个点,m条边的无向连通图。从顶点1出发,往其余所有点分别走一次并返回。
    往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11,路径B为1,3,2,11,路径B字典序较小。注意是序列的字典序的最小,而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回,然后往其他点走,直到所有点都走过。
    可以知道,经过的边会构成一棵最短路径树。请问,在这棵最短路径树上,最长的包含K个点的简单路径长度为多长?长度为该最长长度的不同路径有多少条?
    这里的简单路径是指:对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同,点A到点B的路径和点B到点A视为同一条路径。

    Input

    第一行输入三个正整数n,m,K,表示有n个点m条边,要求的路径需要经过K个点。接下来输入m行,每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000),表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。

    Output

    输出一行两个整数,以一个空格隔开,第一个整数表示包含K个点的路径最长为多长,第二个整数表示这样的不同的最长路径有多少条。

    Sample Input

    6 6 4
    1 2 1
    2 3 1
    3 4 1
    2 5 1
    3 6 1
    5 6 1

    Sample Output

    3 4

    HINT

    对于所有数据n<=30000,m<=60000,2<=K<=n。
    数据保证最短路径树上至少存在一条长度为K的路径。
    2016.12.7新加数据一组by - wyxxqz-150137

    题解:做这种题总有一种奇怪的违和感,感觉就是强行把两道题拼起来变成一道题考~

    子任务1:求最短路径树,这个直接Dijkstra+DFS就好,DFS时先走编号小的点。

    子任务2:求树上包含k个点的最长路径的长度及条数,这个显然点分治。在以x为分治中心时,我们依次遍历它的所有儿子的子树,用fl[i]表示在之前的子树中,包含i个点的链的最长路径长度,用fs[i]表示条数;用gl[i]表示在当前的子树中,包含i个点的链的最长路径长度,用gs[i]表示条数,然后搞一搞就行了。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <algorithm>
    #define mp(A,B)	make_pair(A,B)
    #define fir(_) ((_).first)
    #define sec(_) ((_).second)
    using namespace std;
    typedef pair<int,int> pii;
    const int maxn=30010;
    const int inf=0x3f3f3f3f;
    int n,m,K,cnt,root,tot,maxx,ans,sum,d;
    int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],dis[maxn],vis[maxn],dep[maxn];
    int fl[maxn],fs[maxn],gl[maxn],gs[maxn],siz[maxn];
    vector<pii> e[maxn];
    priority_queue<pii> pq;
    void add(int a,int b,int c)
    {
    	//printf("%d %d %d\n",a,b,c);
    	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
    }
    void dijkstra()
    {
    	memset(dis,0x3f,sizeof(dis));
    	dis[1]=0;
    	int i,u;
    	pii y;
    	pq.push(mp(0,-1));
    	while(!pq.empty())
    	{
    		u=-sec(pq.top()),pq.pop();
    		if(vis[u])	continue ;
    		vis[u]=1;
    		for(int i=0;i<e[u].size();i++)
    		{
    			y=e[u][i];
    			if(dis[fir(y)]>dis[u]+sec(y))
    				dis[fir(y)]=dis[u]+sec(y),pq.push(mp(-dis[fir(y)],-fir(y)));
    		}
    	}
    	memset(vis,0,sizeof(vis));
    }
    void Dfs(int x)
    {
    	vis[x]=1;
    	for(int i=0;i<e[x].size();i++)
    	{
    		pii y=e[x][i];
    		if(!vis[fir(y)]&&dis[fir(y)]==dis[x]+sec(y))
    			Dfs(fir(y)),add(x,fir(y),sec(y)),add(fir(y),x,sec(y));
    	}
    }
    void getr(int x,int fa)
    {
    	siz[x]=1;
    	int i,mx=0;
    	for(i=head[x];i!=-1;i=next[i])
    	{
    		if(vis[to[i]]||to[i]==fa)	continue;
    		getr(to[i],x),siz[x]+=siz[to[i]];
    		mx=max(mx,siz[to[i]]);
    	}
    	if(maxx>max(tot-siz[x],mx))	maxx=max(tot-siz[x],mx),root=x;
    }
    void getd(int x,int fa,int dep,int len)
    {
    	if(dep>=K)	return ;
    	d=max(d,dep);
    	if(gl[dep]<len)	gl[dep]=len,gs[dep]=0;
    	if(gl[dep]==len)	gs[dep]++;
    	for(int i=head[x];i!=-1;i=next[i])
    	{
    		if(vis[to[i]]||to[i]==fa)	continue;
    		getd(to[i],x,dep+1,len+val[i]);
    	}
    }
    void dfs(int x)
    {
    	vis[x]=1;
    	int i,j,dd=0;
    	fs[0]=1;
    	for(i=head[x];i!=-1;i=next[i])
    	{
    		if(vis[to[i]])	continue;
    		d=0,getd(to[i],x,1,val[i]),dd=max(dd,d);
    		for(j=1;j<=d;j++)
    		{
    			if(ans<fl[K-j-1]+gl[j])	ans=fl[K-j-1]+gl[j],sum=0;
    			if(ans==fl[K-j-1]+gl[j])	sum+=fs[K-j-1]*gs[j];
    		}
    		for(j=1;j<=d;j++)
    		{
    			if(fl[j]<gl[j])	fl[j]=gl[j],fs[j]=0;
    			if(fl[j]==gl[j])	fs[j]+=gs[j];
    			gl[j]=-inf,gs[j]=0;
    		}
    	}
    	for(i=1;i<=dd;i++)	fl[i]=-inf,fs[i]=0;
    	for(i=head[x];i!=-1;i=next[i])
    	{
    		if(vis[to[i]])	continue;
    		tot=siz[to[i]],maxx=1<<30,getr(to[i],x),dfs(root);
    	}
    }
    int rd()
    {
    	int ret=0,f=1;	char gc=getchar();
    	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}
    	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();
    	return ret*f;
    }
    int main()
    {
    	//freopen("bz4016.in","r",stdin);
    	//freopen("bz4016.out","w",stdout);
    	n=rd(),m=rd(),K=rd();
    	int i,a,b,c;
    	for(i=1;i<=m;i++)	a=rd(),b=rd(),c=rd(),e[a].push_back(mp(b,c)),e[b].push_back(mp(a,c));
    	for(i=1;i<=n;i++)	sort(e[i].begin(),e[i].end());
    	memset(head,-1,sizeof(head));
    	dijkstra(),Dfs(1);
    	memset(vis,0,sizeof(vis));
    	for(i=1;i<=n;i++)	fl[i]=gl[i]=-inf;
    	tot=n,maxx=1<<30,getr(1,0),dfs(root);
    	printf("%d %d",ans,sum);
    	return 0;
    }

    转载于:https://www.cnblogs.com/CQzhangyu/p/7071339.html

    展开全文
  • 首先介绍这三个概念,很多人都听过最短路径了,但是最短路径树却很少听过,关于最短路径树的介绍也不太多。而最短路径树和最小生成树更是完全不同的两个概念。 最短路径就是从一个指定的顶点出发,计算从该顶点出发...
  • 面向互联网AS级拓扑监测应用,提出了一种基于最短路径树SPT覆盖的算法,用于选择部署最少的监测点,发现尽量完整的AS拓扑。该算法求出所有顶点的最短路径树,按照启发式策略选择最小的顶点集合,使集合中节点的最短...
  • 题目大意:①先求任意两点间的最短路径累加和,其中不连通的边权为L ②删除任意一条边,求全局最短路径和的最大值。 解题思路: 首先说下多源最短路中,floyd和和优先队列优化的dijkstra的取舍。floyd比较好拍,...
  • 一种基于神经网络的最短路径树生成算法,屈鸿,,最短路径树的计算是一个典型的组合优化问题,长期以来吸引了很多学者的高度重视。高效的最短路径树生成算法对高效络路由协议的实
  • 最短路径树问题

    千次阅读 2015-11-15 10:17:40
    最短路径树问题时间限制: 1 Sec 内存限制: 128 MB 题目描述 给一个包含n个点,m条边的无向连通图。从顶点1出发,往其余所有点分别走一次并返回。 往某一个点走时,选择总长度最短的路径走。若有多条长度最短的...
  • 最小生成 在图论中,无向图 G 的生成(英语:Spanning Tree)是具有 G 的全部顶点,但边数最少的连通子图。[1] 一个图的生成可能有多个。 带权图的生成中,总权重最小的称为最小生成。 它在实际中有什么...
  • HDU2433 Travel BFS求最短路径树+优化

    千次阅读 2012-01-05 14:28:09
    对于每一个点,做一次BFS,求出以这个点为出发点时的最短路径树的长度和它包含的边 记录长度是用于求值,记录边是用于优化。因为只有处于最短路径树上的边的改动才会影响到结果 如果要去的边的不在最短路径树上,不...
  • BZOJ4016 最短路径树问题  给一个包含n个点,m条边的无向连通图。从顶点1出发,往其余所有点分别走一次并返回。 往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则选择经过的...
  • 最小生成算法:PRIM和 KRUSKAL#include #include #include #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 using namespace std; typedef struct Arcell { dou
  • 题目大意: 有一个n(n)个点m(m)条边的无向图,边权为1,求删掉每一条边之后,每个点到所有点的最短距离和。 多组数据题目分析: 最暴力的方法就是删掉每一条边,...最短路径树就是对于一个源点,到每一个点都有一
  • 若有多条长度最短路径,则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11,路径B为1,3,2,11,路径B字典序较小。注意是序列的字典序的最小,而非路径中节点编号相连的字符串字典序最小)。到达该点后按...
  • 题目大意大概就是要根据规定的一些条件...然后进行分治,首先我们开一个数组a[i]保存经过i条边的路径的最大长度,用b[i][j]表示经过i条边路径长度为j的路径条数,然后对于一个点的每棵子树单独处理,现在我们考虑合并
  • HDOJ2433-最短路径树

    2012-08-21 17:35:21
    //1406ms险过。 #include #include #include #include #include using namespace std; const int NN=110; const int MM=3100; struct node{ int v,e;... node(int _v,int _e): v(_v),e(_e) {}
  • 从点u开始的最短路径树是这样一幅图G1= (V, E1),其中E1是E的子集,并且在G1中,u到所有其它点的最短路径与他在G中是一样的。 现在给定一幅无向带权连通图G和一个点u。你的任务是找出从u开始的最短路径树,并且这个...
  • 首先把最短路径树建出来(用\(Dijkstra\),没试过\(SPFA\)\(\leftarrow\)它死了),然后问题就变成了一个关于深度的问题,可以用长链剖分做,所以我们用点分治来做(滑稽)。 有一点要说,这一题数据比较水,如果...
  • 图(5)最短路径树

    2020-02-16 21:54:50
    1、什么是最短路径 这里讨论的是带权有向图和带权无向图,在这类图中一个顶点到其他顶点可能有路径,可能没有路径,也可能有多条不同的路径,怎样找到一条最好的路径呢,这就是本节要讨论的最短路径问题。 定义: 在...
  • hdu2433(最短路径树)

    2017-06-27 14:21:34
    链接:点击打开链接 题意:给出一个n个点m条边的无向图,问删除每一条边后每两个点最短路的和 代码:#include #include #include #include #include #include #include #include ...int x[3005],y
  • 任意个两个城市间的货物运输会选择最短路径,把这n*(n-1)条最短路径的和记为S。现在你来寻找关键公路r,公路r必须满足:当r堵塞之后,S的值会变大(如果r堵塞后使得城市u和v不可达,则S为无穷大)。 输入格式 第1...
  • 城堡是形的并且满足下面的条件:设 Di为如果所有的通道都被修建,第 i 号房间与第 1 号房间的最短路径长度;而 Si为实际修建的形城堡中第 i 号房间与第 1 号房间的路径长度;要求对于所有整数 i (1≤i≤N),有 ...

空空如也

1 2 3 4 5 ... 20
收藏数 6,187
精华内容 2,474
关键字:

最短路径树