利用这一篇博客记录图论中一类典型题的解题记录-分层图

1.P4822 [BJWC2012]冻结

problem4822

解法1- spfa+两个队列维护答案

从与起点相连的每条边开始遍历，一个队列用于维护每次实行松弛操作更新的点，另一个队列维护当前这个点使用的冻结次数，用dist[j][card]表示从起点到j这一点使用card次冻结后的最短距离，然后不断更新答案即可。

解法1-代码

#include <bits/stdc++.h>

using namespace std;

const int N = 60, M = 2e3+100;

int h[N],e[M],w[M],ne[M],idx;
int dist[N][N];
int n,m,k;
queue<int> q;
queue<int> q_sc;    
bool st[N][N];   //st[i][j] 表示到第i个点的最短路径使用了j次冻结的状态是否在队列中

void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}

void spfa(){
    q.push(1);
    q_sc.push(0);
    memset(dist,0x3f,sizeof dist);
    // for(int i = 0; i<=k; i++) dist[1][i] = 0;
    dist[1][0] = 0;
    st[1][0] = true;
    
    while(!q.empty()){
        int t = q.front(), card = q_sc.front();
        q.pop(),q_sc.pop();
        st[t][card] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            
            //不使用冻结
            if(dist[j][card] > dist[t][card] + w[i]){
                dist[j][card] = dist[t][card] + w[i];
                if(!st[j][card]){
                    q.push(j);
                    st[j][card] = true;
                    q_sc.push(card);
                }
            }
            
            //使用冻结
            if(dist[j][card+1] > dist[t][card] + w[i]/2){
                dist[j][card+1] = dist[t][card] + w[i]/2;
                if(!st[j][card+1] && card<k){
                    q.push(j);
                    st[j][card+1] = true;
                    q_sc.push(card+1);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    
    spfa();
    // cout<<dist[4][0] << " " << dist[4][1]<<endl;
    int ans = 1e9;
    for(int i = 0; i<=k; i++){
        ans = min(ans,dist[n][i]);
    }
    cout<<ans;
    return 0;
}

解法2-分层图

对于分层图个人理解就是，每一层的所有节点之间边的权值与第0层的一致，但每一层之间边的权值不相同，假设在第i层有u，v两点，u到v的代价是w，那么在第i+1层的u'和v'之间的权值也为w，但u与v' 以及 v 与 u'的权值在这一题中就为w/2，也就是在同层之间旅行，边权的代价不变，但是在不同层之间旅行，边权就会按照题意发生变化，所以一旦分层图建图完毕，在分层图上跑最短路，就能得到这一类问题的答案，另外，对一般分层图的数据范围来说，k的值会给得很小，从下面两题也可以看出来。

解法2-代码

#include <bits/stdc++.h>

using namespace std;

const int N = 60*600, M = 2e5+100;

int h[N], e[M],ne[M],w[M],idx;
int n,m,k;
bool st[N];
int dist[N];

void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}

void spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    
    memset(h,-1,sizeof h);
    while(m--){
        int x,y,c;
        cin>>x>>y>>c;
        for(int i = 0; i<=k; i++){
            //第i层
            add(x+i*n,y+i*n,c);
            add(y+i*n,x+i*n,c);
            if(i<k){
                add(x+i*n,y+(i+1)*n,c/2);
                add(y+i*n,x+(i+1)*n,c/2);
            }
        }
    }
    
    spfa();
    
    int ans = 1e9;
    for(int i = 1; i<=k+1; i++){
        ans = min(ans,dist[i*n]);
    }
    cout<<ans;
    return 0;
}

2.P2939 [USACO09FEB]Revamping Trails G

problem2939

分析

一样的思路，只不过这里用dijkstra来跑最短路。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 20*100000, M = 5e4*4*30;

int h[N], e[M],w[M],ne[M],idx;
int n,m,k;
int dist[N];
bool st[N];

typedef pair<int,int> PII;
void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0,1});
    while(!q.empty()){
        auto a = q.top();
        q.pop();
        int t = a.second, distance = a.first;
        
        if(st[t]) continue;
        st[t] = true;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                q.push({dist[j],j});
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    
    memset(h,-1,sizeof h);
    
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        for(int i = 0; i<=k; i++){
            add(a+i*n,b+i*n,c);
            add(b+i*n,a+i*n,c);
            if(i<k){
                add(a+i*n,b+(i+1)*n,0);
                add(b+i*n,a+(i+1)*n,0);
            }
        }
    }
    
    dijkstra();
    
    int ans = 1e9;
    for(int i = 1; i<=k+1; i++){
        ans = min(ans,dist[n*i]);
    }
    cout<<ans;
    return 0;
}

3.P4568 [JLOI2011]飞行路线

problem4586

分析

与第二题代码除了数据范围不一样，其他同。

代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
const int N = 2e6+100, M = 1e7+100;

int n,m,k,s,td;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,s});
    
    while(!heap.empty()){
        PII a = heap.top();
        heap.pop();
        int t = a.second, distance = a.first;
        if(st[t]) continue;
        st[t] = true;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > w[i] + distance){
                dist[j] = w[i] + distance;
                heap.push({dist[j],j});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&td);
    // s++, td++;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        // a++, b++;
        for(int i = 0; i<=k; i++){
            add(a+i*n,b+i*n,c);
            add(b+i*n,a+i*n,c);
            if(i<k){
                add(a+i*n,b+(i+1)*n,0);
                add(b+i*n,a+(i+1)*n,0);
            }
        }
    }
    
    dijkstra();
    
    int ans = 1e8;
    for(int i = 0; i<=k; i++){
        ans = min(ans,dist[td+i*n]);
        // cout<<i<<" "<<dist[i*td]<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

图论-分层图