精华内容
下载资源
问答
  • 最短路径生成树: ([HAOI2012]道路) 题目描述 C国有n座城市,城市之间通过m条[b]单向[/b]道路连接。一条路径被称为最短路,当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同,当且仅...

    最短路径生成树

    ([HAOI2012]道路)

    题目描述

    C国有n座城市,城市之间通过m条[b]单向[/b]道路连接。一条路径被称为最短路,当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同,当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估,评估方式为计算有多少条不同的最短路经过该道路。现在,这个任务交给了你。

    输入输出格式

    输入格式:

    第一行包含两个正整数n、m

    接下来m行每行包含三个正整数u、v、w,表示有一条从u到v长度为w的道路

    输出格式:

    输出应有m行,第i行包含一个数,代表经过第i条道路的最短路的数目对[b]1000000007取模[/b]后的结果

    输入输出样例

    输入样例#1:

    4 4
    1 2 5
    2 3 5
    3 4 5
    1 4 8

    输出样例#1:

    2
    3
    2
    1

    说明

    数据规模

    30%的数据满足:n≤15、m≤30

    60%的数据满足:n≤300、m≤1000

    100%的数据满足:n≤1500、m≤5000、w≤10000

    个人思路:

    • 枚举源点S,跑最短路径生成树,在每次得到的DAG上进行拓扑排序计数即可(正向反向各一次,计数依据乘法原理)

    题目地址:https://www.luogu.org/problemnew/show/P2573

    参考代码:

    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    inline int read() {
        int res = 0; bool bo = 0; char c;
        while (((c = getchar()) < '0' || c > '9') && c != '-');
        if (c == '-') bo = 1; else res = c - 48;
        while ((c = getchar()) >= '0' && c <= '9')
            res = (res << 3) + (res << 1) + (c - 48);
        return bo ? ~res + 1 : res;
    }
    const int N = 1505, M = 5005, INF = 0x3f3f3f3f, PYZ = 1e9 + 7;
    int n, m, ecnt, nxt[M], adj[N], st[M], go[M], val[M], dis[M], len, que[M << 1],
    cnt[N], cnt1[N], cnt2[N], H, T, tot, q[N], ans[M];
    bool vis[N], ins[M];
    void add_edge(int u, int v, int w) {
        nxt[++ecnt] = adj[u]; adj[u] = ecnt; st[ecnt] = u; go[ecnt] = v; val[ecnt] = w;
    }
    void spfa(int S) {
        int i; memset(dis, INF, sizeof(dis));
        memset(ins, 0, sizeof(ins));
        dis[que[len = 1] = S] = 0;
        for (i = 1; i <= len; i++) {
            int u = que[i]; vis[u] = 0;
            for (int e = adj[u], v; e; e = nxt[e])
                if (dis[u] + val[e] < dis[v = go[e]]) {
                    dis[v] = dis[u] + val[e];
                    if (!vis[v]) vis[que[++len] = v] = 1;
                }
        }
        for (i = 1; i <= m; i++)
            if (dis[st[i]] + val[i] == dis[go[i]])
                ins[i] = 1;
    }
    void topo(int S) {
        memset(cnt, 0, sizeof(cnt));
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        int i; H = tot = 0; cnt1[que[T = 1] = S] = 1;
        for (i = 1; i <= m; i++) if (ins[i]) cnt[go[i]]++;
        while (H < T) {
            int u = que[++H]; q[++tot] = u;
            for (int e = adj[u], v; e; e = nxt[e]) {
                if (!ins[e]) continue;
                v = go[e]; if (!(--cnt[v])) que[++T] = v;
                (cnt1[v] += cnt1[u]) %= PYZ;
            }
        }
        for (i = tot; i; i--) {
            int u = q[i]; cnt2[u]++;
            for (int e = adj[u], v; e; e = nxt[e]) {
                if (!ins[e]) continue;
                (cnt2[u] += cnt2[v = go[e]]) %= PYZ;
            }
        }
    }
    void solve(int S) {
        int i; spfa(S); topo(S);
        for (i = 1; i <= m; i++) if (ins[i])
            (ans[i] += 1ll * cnt1[st[i]] * cnt2[go[i]] % PYZ) %= PYZ;
    }
    int main() {
        int i, x, y, z; n = read(); m = read();
        for (i = 1; i <= m; i++) x = read(), y = read(),
            z = read(), add_edge(x, y, z);
        for (i = 1; i <= n; i++) solve(i);
        for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
        return 0;
    }

    最小生成树:

    ([SCOI2012]滑雪)

    题目描述

    a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1≤i≤N)和一高度H_i。a180285能从景点ii滑到景点jj当且仅当存在一条i和j之间的边,且ii的高度不小于j。 与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是a180285 滑行的距离)。请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。 现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?

    输入输出格式

    输入格式:

    输入的第一行是两个整数N,M。

    接下来1行有N个整数H_i,分别表示每个景点的高度。

    接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,U_i,V_i,K_i​。表示编号为U_iU的景点和编号为V_i的景点之间有一条长度为K_i的轨道。

    输出格式:

    输出一行,表示a180285最多能到达多少个景点,以及此时最短的滑行距离总和。

    输入输出样例

    输入样例#1:

    3 3 
    3 2 1 
    1 2 1 
    2 3 1 
    1 3 10

    输出样例#1:

    3 2

    说明

    【数据范围】

    对于30\%的数据,保证 1 \le N \le 2000

    对于100\%的数据,保证 1 \le N \le 10^5

    对于所有的数据,保证 1 \le M \le 10^6 , 1 \le H_i \le 10^91 \le K_i \le 10^9

    个人思路:由题意可以发现,正解为求一个从源点1出发的最小生成树,在Kruskal的过程中,将终点的高度作为第一关键字,边权作为第二关键字,结果即为最短滑行距离总和

    题目地址:https://www.luogu.org/problemnew/show/P2573

    参考代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<cstdlib>
    #include<string>
    #include<queue>
    #include<map>
    #include<vector>
    #define ll long long
    #define R register
    #define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
    #define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
    using namespace std;
    const int N=2000000+5,M=100000+5;
    ll n,m,tot,ans,num,sum,cnt,ql,qr;
    struct it{
        ll u,v,w;//新图 
    };
    struct node {
        ll to,nx,val;//初始图(链式前向星) 
    };
    it a[N];node b[N];
    ll fa[M],h[M],head[M],q[M];
    bool vis[M];
    inline ll read()//读入优化 
    {
        ll x=0,f=1;char ch=getchar();
        while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
        return x*f;
    }
    bool cmp1(it x,it y) {
    //比较函数,以终点的高度为第一关键字从大到小排序,边长为第二关键字从小到大排序 
        if(h[x.v]!=h[y.v]) return h[x.v]>h[y.v];
        return x.w<y.w;
    }
    inline ll find(ll x) {//并查集找父亲 
        if(fa[x]!=x) fa[x]=find(fa[x]);
        return fa[x];
    }
    inline void add(int u,int v,int c) {//链式前向星加边 
        b[++num].to=v;
        b[num].nx=head[u];
        head[u]=num;
        b[num].val=c;
    }
    void bfs(){//宽搜,拓展可到达的点,建新图 
        q[++qr]=1;vis[1]=1;
        while(ql<qr) {
            int now=q[++ql];
            for(int i=head[now];i;i=b[i].nx) {
                a[++cnt].u=now;a[cnt].v=b[i].to;a[cnt].w=b[i].val;//建立新图的边 
                if(!vis[b[i].to]) {
                    vis[b[i].to]=1;sum++;//sum计数器计可到达的点 
                    q[++qr]=(b[i].to);
                }
            }
        }
    }
    int main()
    {
    //    freopen("steep.in","r",stdin);
    //    freopen("steep.out","w",stdout);
        n=read();m=read();//读入数据 
        Rf(i,1,n) h[i]=read(),fa[i]=i;
        Rf(i,1,m) {
            R int u=read(),v=read(),c=read();
            if(h[u]>=h[v]) add(u,v,c);//根据边两边的点的高度,建立一条由高到低的单向边 
            if(h[u]<=h[v]) add(v,u,c);//当高度相等时会建两条边 
        }
        bfs();//广搜拓展点 
        sort(a+1,a+1+cnt,cmp1);//对新图的点跑Kruskal求最小生成树 
        Rf(i,1,cnt) {
            R int rx=find(a[i].u),ry=find(a[i].v);
            if(rx!=ry) {
                fa[rx]=ry;ans+=a[i].w;//求最短距离 
            }
        }
        printf("%lld %lld",sum+1,ans);//sum+1,还有初始的1点可到 
        return 0;
    }
    展开全文
  • WA,给的那个测试用例可以通过 #include<bits/stdc++.h>...求把点连起来的最小路径,kruskal?dijkstra? */ int main(){ //kruskal用到并查集 //dijkstra不用 int n; while(cin>>n)...

     WA,给的那个测试用例可以通过(因为给的用例就是简单的三个点,头到尾,最短路径等于最小生成树)

    #include<bits/stdc++.h>
    using namespace std;
    /*
    求把点连起来的最小路径,kruskal?dijkstra?
    */
    
    
    
    int main(){
        //kruskal用到并查集
        //dijkstra不用
        int n;
        
            while(cin>>n)
            {
                vector<vector<float>>dist(n,vector<float>(n,0));//存放点i到j的距离
                vector<vector<float>>pos(n,vector<float>(2,0));//存放点的坐标
                
                for(int i=0;i<n;i++)
                {
                    for(int j=0;j<2;j++)
                    {
                        cin>>pos[i][j];
                    }
                }
                
                for(int i=0;i<n;i++)//初始化dist矩阵,i到j的距离
                {
                    for(int j=0;j<n;j++)
                    {
                        if(i==j){continue;}
                        int dx=pos[i][0]-pos[j][0];
                        int dy=pos[i][1]-pos[j][1];
                        dist[i][j]=sqrt(dx*dx+dy*dy);
                    }
                }
                //cout<<setprecision(3)<<dist[1][0];
                
                //初始化dis数组,第一个dis数组以0号坐标点开始
                float ans=0;
                
                vector<int>visted(n,0);
                visted[0]=1;
                vector<float>dis(n,0);
                int tmppos;
                vector<int>load(n,0);
                
                for(int i=1;i<n;i++)
                {
                    dis[i]=dist[0][i];
                }
                
                for(int t=1;t<n;t++)//循环n
                {    int mindis=INT_MAX;
                    for(int i=1;i<n;i++)
                    {
                        //找到dis中最近的
                        if(visted[i]!=1&&dis[i]<mindis)
                        {
                            mindis=dis[i];
                            tmppos=i;
                        }
                    }
                     visted[tmppos]=1;
                     //cout<<dis[tmppos];
                     //ans+=dis[tmppos];
                     load[t]=tmppos;
                    //找到最近的下一个点tmppos,从这里更新dis
                    for(int i=1;i<n;i++)
                    {
                        if(visted[i]!=1&&dis[tmppos]+dist[tmppos][i]<dis[i])//经过tmppos这个点的中转,更新dis数组
                        {//如果经中转后更近,那么更新dis
                            dis[i]=dis[tmppos]+dist[tmppos][i];
                        }
                    }
                 
                 
                }
                
                //for_each(load.begin(),load.end(),[](int val){cout<<val<<" ";});
                for(int i=1;i<n;i++)
                {
                    ans+=dist[i][i-1];
                }
                cout<<setprecision(3)<<ans<<endl;
            }
        
        
        return 0;
    }

    上面的dijkstra行不通,两个点间存在最短路径并不代表最后的生成树最小

    换prim

    load表示已经选取的节点

    #include<bits/stdc++.h>
    using namespace std;
    /*
    求把点连起来的最小路径,kruskal?dijkstra?
    */
    
    
    
    int main(){
        //kruskal用到并查集
        //dijkstra不用
        int n;
        
            while(cin>>n)
            {
                vector<vector<double>>dist(n,vector<double>(n,0));//存放点i到j的距离
                vector<vector<double>>pos(n,vector<double>(2,0));//存放点的坐标
                
                for(int i=0;i<n;i++)
                {
                    for(int j=0;j<2;j++)
                    {
                        cin>>pos[i][j];
                    }
                }
                
                for(int i=0;i<n;i++)//初始化dist矩阵,i到j的距离
                {
                    for(int j=0;j<n;j++)
                    {
                        if(i==j){continue;}
                        int dx=pos[i][0]-pos[j][0];
                        int dy=pos[i][1]-pos[j][1];
                        dist[i][j]=sqrt(dx*dx+dy*dy);
                    }
                }
                //cout<<setprecision(3)<<dist[1][0];
                
                //初始化dis数组,第一个dis数组以0号坐标点开始
                double ans=0;
                
                vector<int>visted(n,0);
                visted[0]=1;
                vector<double>dis(n,0);
                int tmppos;
                vector<int>load(n,0);
                int k;
                
                for(int i=1;i<n;i++)
                {
                    dis[i]=dist[0][i];
                }
                
                for(int t=1;t<n;t++)//dijkstraWA了,换prim
                {    
                    double mindis=INT_MAX;
                    //min_edge=Max;
                    for(int i=0;i<t;i++)//在所有已选取的点中
                    {
                        for(int j=0;j<n;j++)//找距离最小且未访问过的边
                        {
                            if(dist[load[i]][j]<mindis&&visted[j]!=1)
                            {
                                mindis=dist[load[i]][j];
                                k=j;
                            }
                        }
                    }//寻找最小生成树中节点到其它节点最小的边。
                    load[t]=k;//将该节点加入到最小生成树节点集合
                    visted[k]=true;
                    //cout<<mindis<<" ";
                    ans=ans+mindis;//将该边的长度加入到sum中
    
                    
                }
        cout<<setprecision(6)<<ans<<endl;
                //cout<<dist[0][1];
            }
        return 0;
    }

     

    展开全文
  • 最短路径树简谈

    2020-12-05 17:05:04
    在最开始,我们要知道最短路径树是个什么东西,不同最小生成树最短路径树是选一个节点为根,得到一颗树上的所有点,原图中根节点到其的最短距离相等。 因为很多要用到边的记录,然而我比较菜只会用链式前向星...

    在最开始,我们要知道最短路径树是个什么东西,不同于最小生成树,最短路径树是选一个节点为根,得到一颗树上的所有点,与原图中根节点到其的最短距离相等。

    因为很多要用到边的记录,然而我比较菜只会用链式前向星方便的记录边,所以在写最短路路径树的过程中全用的链式前向星存图(

    先来个比较板子的

    CF545E Paths and Trees

    题意:给定一张带正权的无向图和一个源点,求边权和最小的最短路径树。

    思路:在跑dij的过程中记录每个点的前驱边,因为题目要求边权和最小,所以如果遇到相同的最短距离,我们应该选取前驱边更小的那一个,然后累加所有点的前驱边边权并排序输出答案即可。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    typedef pair<int,int>pii;
    constexpr int maxn=6e5+5,inf=0x3f3f3f3f;
    int n,m,k,t,cnt=0,head[maxn],ans=0;
    int vis[maxn],dis[maxn],pre[maxn],a[maxn];
    struct edge{
    	int v,w,nex;
    }e[maxn];
    inline void add(int u,int v,int w){
    	e[++cnt].v=v;
    	e[cnt].w=w;
    	e[cnt].nex=head[u];
    	head[u]=cnt;
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    void dij(int s){
    	memset(dis,inf,sizeof dis);
    	dis[s]=0;
    	q.push({0,s});
    	while(!q.empty()){
    		auto x=q.top();
    		q.pop();
    		int u=x.second;
    		if(vis[u])continue;
    		vis[u]=1;
    		for(int i=head[u];i;i=e[i].nex){
    			int v=e[i].v;
    			int w=e[i].w;
    			if(dis[v]>dis[u]+w){
    				pre[v]=i;
    				dis[v]=dis[u]+w;
    				q.push({dis[v],v});
    			}
    			else if(dis[v]==dis[u]+w){
    				if(e[pre[v]].w>e[i].w){
    					pre[v]=i;
    				}
    			}
    		}
    	}
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
    	}
    	int st;
    	cin>>st;
    	dij(st);
    	for(int i=1;i<=n;i++){
    		ans+=e[pre[i]].w;
    	}
    	for(int i=1;i<=n;i++){
    		a[i]=(pre[i]+1)/2;
    	}
    	sort(a+1,a+1+n);
    	cout<<ans<<endl;
    	for(int i=2;i<=n;i++){
    		cout<<a[i]<<" ";
    	}
    	return 0;
    }
    
    
    
    

    CF1076D Edge Deletion

    题意:给一个nn个点,mm条边的无向简单带权连通图, 要求删边至最多剩余kk条边.
    定义"好点"是指删边后, 11号节点到它的最短路长度仍然等于原图最短路长度的节点.
    最大化删边后的好点个数.

    思路:跑dij记录最短路径树的前驱边,最后DFSDFS输出答案

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    typedef pair<int,int>pii;
    constexpr int maxn=6e5+5,inf=0x3f3f3f3f;
    int n,m,k,t,cnt=0,head[maxn],ans=0;
    int vis[maxn],dis[maxn],pre[maxn],a[maxn],vis1[maxn];
    struct edge{
    	int v,w,nex;
    }e[maxn];
    inline void add(int u,int v,int w){
    	e[++cnt].v=v;
    	e[cnt].w=w;
    	e[cnt].nex=head[u];
    	head[u]=cnt;
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    void dij(int s){
    	memset(dis,inf,sizeof dis);
    	dis[s]=0;
    	q.push({0,s});
    	while(!q.empty()){
    		auto x=q.top();
    		q.pop();
    		int u=x.second;
    		if(vis[u])continue;
    		vis[u]=1;
    		for(int i=head[u];i;i=e[i].nex){
    			int v=e[i].v;
    			int w=e[i].w;
    			if(dis[v]>dis[u]+w){
    				pre[v]=i;
    				dis[v]=dis[u]+w;
    				q.push({dis[v],v});
    			}
    			else if(dis[v]==dis[u]+w){
    				if(e[pre[v]].w>e[i].w){
    					pre[v]=i;
    				}
    			}
    		}
    	}
    }
    void dfs(int u){
    	if(!k)return;
    	for(int i=head[u];i;i=e[i].nex){
    		int v=e[i].v;
    		if(!vis1[i]&&pre[v]==(i)&&ans<k){
    			ans++;
    			a[ans]=i;
    			vis1[i]=1;
    			dfs(v);
    		}
    	}
    }
    signed main(){
    	cin>>n>>m>>k;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
    	}
    	dij(1);
    	
    	dfs(1);
    	
    	printf("%d\n",min(n-1,k));
    	for(int i=1;i<=ans;i++){
    		cout<<(a[i]+1)/2<<" ";
    	}
    	return 0;
    }
    
    
    
    

    AcWing349.黑暗城堡

    题意:求最短路径树的方案数

    思路:在跑dij的过程中,记录方案即可(其实就是个最短路计数?)

    看似有难度其实水的一批

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    typedef pair<int,int>pii;
    constexpr int maxn=100005,inf=0x3f3f3f3f,mod=2147483647;
    
    int n,m,k,t,cnt=0,head[maxn],ans=1;
    int vis[maxn],dis[maxn],v[maxn];
    int pre[maxn];
    
    struct edge{
    	int v,w,nex;
    }e[2000005];
    inline void add(int u,int v,int w){
    	e[++cnt].v=v;
    	e[cnt].w=w;
    	e[cnt].nex=head[u];
    	head[u]=cnt;
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    void dij(int s){
    	memset(dis,inf,sizeof dis);
    	dis[s]=0;
    	q.push({0,s});
    	while(!q.empty()){
    		auto x=q.top();
    		q.pop();
    		int u=x.second;
    		if(vis[u])continue;
    		vis[u]=1;
    		for(int i=head[u];i;i=e[i].nex){
    			int v=e[i].v;
    			int w=e[i].w;
    			if(dis[v]>dis[u]+w){
    				pre[v]=1;
    				dis[v]=dis[u]+w;
    				q.push({dis[v],v});
    			}
    			else if(dis[v]==dis[u]+w){
    				pre[v]++;
    			}
    		}
    	}
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
    	}
    	dij(1);
    	for(int i=2;i<=n;i++){
    		ans=ans*pre[i]%mod;
    	}
    	cout<<ans;
    	return 0;
    }
    

    CF1005F Berland and the Shortest Paths

    题意:求k条最短路径树方案,若不足k条则输出所有可行方案

    思路:记录每个点的所有前驱边,递归回溯输出方案

    黑暗城堡的加强版本

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    typedef pair<int,int>pii;
    constexpr int maxn=4e5+5,inf=0x3f3f3f3f,mod=1ll<<31-1;
    
    int n,m,k,t,cnt=0,head[maxn],ans=1;
    int vis[maxn],dis[maxn],v[maxn];
    vector<int>pre[maxn];
    
    struct edge{
    	int v,w,nex;
    }e[maxn];
    inline void add(int u,int v,int w){
    	e[++cnt].v=v;
    	e[cnt].w=w;
    	e[cnt].nex=head[u];
    	head[u]=cnt;
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    void dij(int s){
    	memset(dis,inf,sizeof dis);
    	dis[s]=0;
    	q.push({0,s});
    	while(!q.empty()){
    		auto x=q.top();
    		q.pop();
    		int u=x.second;
    		if(vis[u])continue;
    		vis[u]=1;
    		for(int i=head[u];i;i=e[i].nex){
    			int v=e[i].v;
    			int w=e[i].w;
    			if(dis[v]>dis[u]+w){
    				pre[v].clear();
    				pre[v].push_back(i);
    				dis[v]=dis[u]+w;
    				q.push({dis[v],v});
    			}
    			else if(dis[v]==dis[u]+w){
    				/*if(e[pre[v]].w>e[i].w){
    					pre[v]=i;
    				}*/
    				pre[v].push_back(i);
    			}
    		}
    	}
    }
    void dfs(int x){
    	if(x>n){
    		for(int i=1;i<=m;i++){
    			printf("%d",v[i]);
    		}
    		puts("");
    		t++;
    		if(t==k){
    			exit(0);
    		}
    		return;
    	}
    	for(auto i:pre[x]){
    		v[(i+1)/2]=1;
    		dfs(x+1);
    		v[(i+1)/2]=0;
    	}
    }
    signed main(){
    	cin>>n>>m>>k;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v;
    		add(u,v,1);
    		add(v,u,1);
    	}
    	dij(1);
    	for(int i=2;i<=n;i++){
    		ans=ans*pre[i].size();
    		if(ans>k){
    			ans=k;
    			break;
    		}
    	}
    	cout<<ans<<endl;
    	dfs(2);
    	return 0;
    }
    
    
    展开全文
  • 最短路径: Floyd- Warshall算法: 这个算法就是让我们去寻找从点i到点j的距离,有以下两种情况: (1). 两点直接到达的距离最短。 (2). 两点之间通过1个或者1个以上节点连接到达的距离最短。 其中主要代码只有五...

    暑假过去两个月,再一次对一些算法的复习:

    最短路径:

    Floyd- Warshall算法:

    这个算法就是让我们去寻找从点i到点j的距离,有以下两种情况:
    (1). 两点直接到达的距离最短。
    (2). 两点之间通过1个或者1个以上节点连接到达的距离最短。
    其中主要代码只有五行,通过不同的点去中转看看中转之后的点到达的距离与直接到达是否小,如果小就更新距离。

    for(k=1;k<=n;k++)
    	for(i=1;i<=n;i++)
    		for(j=1;j<=n;j++)
    			if(e[i][j]>e[i][k]+e[k][j])
    				e[i][j]=e[i][k]+e[k][j]  
    

    Dijkstra算法:

    这个算法就是找到一个顶点,然后看看这个顶点到其他点的最小距离。如果到下一个顶点的距离比当前顶点大,九成新更新距离。
    具体步骤:
    1、将所有顶点分为两部分:已知最短距离路程的顶点集合P和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P只有一个顶点。我们这里用一个book记录那些点已经在集合P中。
    2、设置源点s到自己的距离为0,若有源点能直接到达顶点,则距离为e[s][i],若不能到达此时距离为无穷大,这个我们定义99999999为无穷大。
    3、在集合Q的所有顶点中选择离源点s最近的顶点u加入集合P中,并考察以u为起点的边,对每一条边进行松弛。
    4、重复第3步,直到集合Q为空。

    for(i=1;i<=n-1;i++)
    	{
    		min=inf;
    		//找到离1号顶点最近的点 
    		for(j=1;j<=n;j++)
    		{
    			if(book[j]==0&&dis[j]<min)
    			{
    				min=dis[j];
    				u=j;
    			}
    		}
    		book[u]=1;
    		for(v=1;v<=n;v++)
    		{
    			if(e[u][v]<inf)
    			{
    				if(dis[v]>dis[u]+e[u][v])
    					dis[v]=dis[u]+e[u][v];
    			}
    		}
    	}
    

    最小生成树:

    kruskal算法:
    先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。
    这个算法实现就是先利用快排把从小到大排序,贪心算法取最优边,然后利用并查集判断两边是否已经在一个集合中。
    核心代码:

    	for(i=1;i<=m;i++)//开始从小到大枚举每一条边
    	{
    		if(merge(e[i].u,e[i].v))//利用并查集判断两个边是否已经在一个集合中
    		{
    			count++;
    			sum=sum+e[i].w;
    		}
    		if(count==n-1)//到n-1条边后退出循环
    			break;
    	}
    
    

    prim算法:
    算法流程:
    1、从任意一个顶点构造生成树,然后用book[]数组记录标记的点。
    2、用dis[]数组记录生成树到各个顶点的距离
    3、从dis[]数组中选出离生成树最近的顶点加入生成树中,如果dis[k]>e[j][k],则重新更新dis[k]。
    4、重复第三步,直到count==n.
    核心代码:

    	book[1]=1;//将1号顶点加入生成树
    	count++;
    	while(count<n)
    	{
    		min=inf;
    		for(i=1;i<=n;i++)
    		{
    			if(book[i]==0&&dis[i]<min)
    			{
    				min=dis[i];
    				j=i;
    			}
    		}
    		book[j]=1;
    		count++;
    		sum+=dis[j];
    		for(k=1;k<=n;k++)//扫描当前j所在的顶点,再以j为中间点,更新生成树到每一个非树顶点的位置 
    		{
    			if(book[k]==0&&dis[k]>e[j][k])
    				dis[k]=e[j][k];
    		}
    	}
    
    

    dp:

    对于用动态规划的问题,其大大的减少了计算量,丰富了计算,它包括:背包问题(详解参照https://blog.csdn.net/qq_44859533/article/details/98972091)、动态三角形、还有最长、最大连续子序列。
    最长连续子序列例题:

    A numeric sequence of ai is ordered if a1 < a2 < … < aN.Let the subsequence of the given numeric sequence ( a1, a2, …, aN) be any sequence ( ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
    Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

    Input
    The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
    Output
    Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
    Sample Input

    7
    1 7 3 5 9 4 8
    

    Sample Output

    4
    

    解题思路:给定一个序列找出连续的递增子序列;

    程序代码:

    #include<stdio.h>
    int main()
    {
    	int i,j,k,n,t;
    	int a[2000];
    	int len[2000];
    	int max;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    		scanf("%d",&a[i]);
    	len[1]=1;
    	for(i=2;i<=n;i++)
    	{
    		t=0;
    		for(k=1;k<i;k++)
    		{
    			if(a[k]<a[i]&&t<len[k])
    				t=len[k];
    		}
    		len[i]=t+1;
    	}
    	max=-1;
    	for(i=1;i<=n;i++)
    	{
    		if(max<len[i])
    			max=len[i];
    	}
    	printf("%d\n",max);
    	return 0;
    }
    
    展开全文
  • 这是一个构建最小生成树的简单算法: 设G=(V,E)是一个图,V有n个顶点,则利用krusal构建最小生成树的过程如下: (1)初始时选取所有的n个顶点构成孤立点的子图T={} (2)将边集E按权值递增的顺序排序,顺序的检查边...
  • 4. 最小生成树 4.1 生成树 (1)定义:所有顶点均由边连接在一起,但不存在回路的图叫该图的生成树 (2)深度优先生成树与广度优先生成树 (3)  一个图可以有许多棵不同的生成树  所有生成树具有以下...
  • prim算法是解决最小生成树问题,也就是权值最小问题。 而 dijkstra算法解决的是最短路径问题。二者相似的点在于都是解决图的边的算法。 并且最关键的特点是都是从一点(起点)开始,进行向外其他未遍历过点的拓展。 ...
  • 数据结构算法系列教程:Dijkstra最短路径 目录数据结构算法系列教程:...  Dijkstra算法允许我们在图的任意两个顶点之间找到最短路径,它不同最小生成树,因为两个顶点之间的最短距离可能不包括图的所有顶点...
  • 更新将以目录形式记录,不同算法的实例相关说明。 ·【v0.01】README文档说明更新 ·【v0.02】SelectionSort排序算法更新,com.myself.algorithm.sort.SelectionSort.class ·【v0.03】template泛型模板函数传参,...
  • 最短路径问题(Shortest Path)——图】

    千次阅读 多人点赞 2020-11-15 23:16:08
    注意:最短路径与最小生成树不同,路径上不一定包含n个顶点。 对于图来说:从一个顶点到另一个顶点可能存在多条路径,每条路径的所包含的边数可能不同。把所包含的边数最少的那条称为最短路径 最短路径:对于网...
  • 最小生成树 1、概念 生成树(要求连通但是没有回路) 一个图可以有许多颗不同的生成树 所有生成树的共同特点: 生成树的顶点个数图的顶点个数相同 生成树是图的极小连通子图,去掉一条边则非连通 一个有n个...
  • 最短路径与最小生成树主要有三点不同最短路径操作对象是有向图(网),而最小生成树的操作对象是无向图(网)。 最短路径有一个明确的始点,而最小生成树没有。 最短路径更新的是始点到每个顶点的路径最短,而最...
  • java 最短路径

    千次阅读 2019-03-29 15:00:20
    思想有点想普利姆算法,利用不断遍历顶点,得到起点到每个顶点的最短路径(普利姆算法得到的是相互连通且相邻的两顶点,前一个顶点到下一个顶点的最小权值,从而形成最小生成树,因此普利姆算法不同的就是我们要的...
  • 最短路径 经典用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短? 交通网络用有线网来表示: ...注意:最短路径与最小生成树不同,路径上不一定包含nnn
  • 最短路径最小生成树在应用很是不同的,比如:一开始修建一条地铁,然后在地铁点上有多个点,需要修建一个路程最短的地铁线,将这些地铁点连接起来,这就是最小生成树(点点之间距离是已知的)。小强需要从A点去B...
  • 由浙江大学计算机科学技术学院考试中心负责考试的组织、日常管理和具体实施工作。 每年分春、秋、冬季组织3次统一考试,考试时间根据场地可用的具体时间而定,大约分别在2-3月、8-9月、11-12月举行。 每场考试分两...
  • 最小生成树

    2020-03-31 09:29:38
    (1)最小生成树能够保证拓扑图的路径之和最短,但不能保证两点之和最短。 (2)两点的路径最小用最短路径 以下两种算法都是基于贪心的思想,每一步都优先选择权值最小的边,但二者为此达到的方式不同,Kruskal直接...
  • 这两种算法大同小异,prim算法是求最小生成树,在每一次取点的时候,判断两点之间的距离,选出距离最小点,作为起点遍历,然后更新d数组,只需要更新起点,到这个点的最小距离给d[v],而dijkstra算法需要从题目给出起点到该点...
  • Prim算法的思想是:对于原始图G(V,E),建立一个集合S,从图的某个顶点开始(顶点可以是指定顶点,也可以是随机的顶点),逐步从点集V-S中选择到S中顶点距离最小的顶点加入S,并把该条最短路径加入最小生成树。...
  • 讲真,去年学理论的时候就觉得普里姆算法迪杰斯特拉太像了,一个是最小生成树,一个是最短路径,但用的思路都是在余下的当中找当前现有的距离最短的。 迪杰斯特拉伪代码不同之处在于: :将G[u][v]赋值给v...
  • Prim 最小生成树  dijstra 最短路 很像,但是却不同。 前者追求的是,将所有点走一遍,总路径最短,算法是不断更新确定的集合之中的点到集合之外的其他的点的最短距离,全部更新完以后,将这些把所有点连接起来的...
  • 最小生成树Lisp 介绍 经常以各种形式出现的问题是以“等效”方式连接不同的“点”,例如,将它们线程连接而没有创建循环。 另一个典型的问题是计算点对点地图中的最短路径。 有几种能够解决这些已知问题的算法,...
  • 数据结构-最小生成树

    2018-04-13 10:32:45
    prim算法描述:选择任意顶点作为生长点(假设为1号顶点),判断该点与其邻接点之间的距离,选择最短的一条(这是找到的最小生成树的其中一条路径)(假设为3号顶点),判断3号顶点与其邻接点之间的距离(除去1号...
  • Lisp中的最小生成树 介绍 经常以各种形式出现的问题是以“等效”方式连接不同的“点”,例如,将它们线程连接而没有创建循环。 另一个典型的问题是计算点对点地图中的最短路径。 有几种能够解决这些已知问题的...
  • [SCOI2012]滑雪时间...其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。 这是一种很神奇的药物,
  • 1.解析 Prim算法和Dijkstra算法非常类似,他们的伪码几乎相近,只是他们优先队列所排序的键值不同而已。...在后面的博客中会说明最小生成树MST与最短路径的区别。 2.代码实例 [c-sharp]view plainc...
  • 题意a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个... 其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180
  • Description a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是... 其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径...

空空如也

空空如也

1 2 3 4 5 6
收藏数 105
精华内容 42
关键字:

最短路径树与最小生成树不同