专栏文章

建图优化

mmohay
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingc9gz
此快照首次捕获于
2025/12/02 01:57
3 个月前
此快照最后确认于
2025/12/02 01:57
3 个月前
查看原文

分层图

首先讲讲如何分辨是不是分层图优化？
  1. 题目里面出现了一些特殊的位置是有传送等功能。
  2. 题目中对一些点流量限制。
例题
分层图的实现逻辑（基于例题）
我们可以知道例题中，特殊的点是全部点，不过题目有次数限制，我们不用分层图十分复杂。
分层图嘛，顾名思义就是多个图叠在一起了，在这题中有kk次免费，我们就建kk层图，每个结点对下一层图中自己相邻的结点连单向边，不用代价。
接下来我们就可以直接在这么帅气的图上面跑一次最短路即可。
题目里限制了kk次免费，我们在这个图上面跑最短路，最多用kk免费，因为我们跑最短路时，代码走过去这个点以后就不能回去了，就类似一个3d的图，到了下一层就不能回去了。
最后输出的答案就是，kk层图中结点nn的最小值。（因题目而异，有可能是必须走完kk次的）
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int K=15;
const int INF=2147483647;
struct node{
    int u,d;
    bool operator<(const node&a)const{
        return d>a.d;
    }
};
vector<pair<int,int>> g[N*(K+1)];
int dis[N*(K+1)];
bool vis[N*(K+1)];
int n,m,k,s,t;
int main(){
    cin>>n>>m>>k>>s>>t;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        for(int j=0;j<=k;j++){
            int uu=j*n+u,vv=j*n+v;
            g[uu].push_back({vv,w});
            g[vv].push_back({uu,w});
        }
        for(int j=0;j<k;j++){
            int uu=j*n+u,vv=(j+1)*n+v;
            g[uu].push_back({vv,0});
            uu=j*n+v,vv=(j+1)*n+u;
            g[uu].push_back({vv,0});
        }
    }
    for(int i=0;i<=k*n+n;i++)dis[i]=INF;
    dis[s]=0;
    priority_queue<node> q;
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto e:g[u]){
            int v=e.first,w=e.second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
    int ans=INF;
    for(int i=0;i<=k;i++)ans=min(ans,dis[i*n+t]);
    cout<<ans;
    return 0;
}

隐式建图

例题

给定两个不同的质数 startstart 和 endend（都是4位数），每次操作可以改变一个数字（0→90\to9），但改变后的数字必须是44位数且仍是质数。 求从 startstart 到 endend 的最少变换次数。如果无法到达，返回 −1-1。
很明显这道题目,无法把所有的边都建出来,我们可以不预先存储所有边，而是在djikstra时动态生成邻居连起就行了。
代码不放了
作者偷懒

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...