【图论】分层图 / 拆点

大多数都是同一个套路，将图拆开成几个图，每一层都对应着一个不同的状态，比如把到点 i 的状态拆成经过了 j 次操作所得的 xx 结果，一般数据不会很大

目前遇到的可分为 3 类：

①.给你最多 k 次操作，求 xx 结果

②.初始给你 k 个燃料，走边需要消耗，每个点你可以选择增加燃料或者不增加燃料，求 xx 结果

③.特殊题（还没见过很多）

P1948 [USACO08JAN] Telephone Lines S - 洛谷

思路：

注意本题的中价值只关于最大值，所以需要改变一下模板

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,m,k;
//走到 i 用了 j 次
int dis[1005][10005];

vector<vector<pair<int,int>>> g(10005);

void solve()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int u,v,t;
        cin >> u >> v >> t;
        g[u].emplace_back(v,t);
        g[v].emplace_back(u,t);
    }
    if(k >= m)
    {
        cout << "0\n";
        return;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = 1e18;
        }  
    }
    //时间 次数 点
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> pq;
    pq.push({0,0,1});
    while (!pq.empty())
    {
        auto [ut,uk,u] = pq.top();
        pq.pop();
        if(dis[u][uk] < ut || u == n)continue;
        for(auto & [v,w] : g[u])
        {
            if(dis[v][uk] > max(dis[u][uk],w))
            {
                dis[v][uk] = max(dis[u][uk],w);
                pq.push({dis[v][uk],uk,v});
            }
            if(uk < k && dis[v][uk+1] > dis[u][uk])
            {
                dis[v][uk+1] = dis[u][uk];
                pq.push({dis[v][uk+1],uk+1,v});                
            }
        }
    }
    int ans = 1e18;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans,dis[n][i]);
    }
    cout << (ans == 1e18 ? -1 : ans) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

P2939 [USACO09FEB] Revamping Trails G - 洛谷

思路：

模板直接套，改改数据范围

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,m,k;
//走到 i 用了 j 次
int dis[10005][55];

vector<vector<pair<int,int>>> g(10005);

void solve()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int u,v,t;
        cin >> u >> v >> t;
        g[u].emplace_back(v,t);
        g[v].emplace_back(u,t);
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = 1e18;
        }  
    }
    //时间 次数 点
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> pq;
    pq.push({0,0,1});
    while (!pq.empty())
    {
        auto [ut,uk,u] = pq.top();
        pq.pop();
        if(dis[u][uk] < ut || u == n)continue;
        for(auto & [v,w] : g[u])
        {
            if(dis[v][uk] > dis[u][uk] + w)
            {
                dis[v][uk] = dis[u][uk] + w;
                pq.push({dis[v][uk],uk,v});
            }
            if(uk < k && dis[v][uk+1] > dis[u][uk])
            {
                dis[v][uk+1] = dis[u][uk];
                pq.push({dis[v][uk+1],uk+1,v});                
            }
        }
    }
    int ans = 1e18;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans,dis[n][i]);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

P4568 [JLOI2011] 飞行路线 - 洛谷

思路：

模板本板，属于机会固定型

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

vector<vector<pair<int, int>>> g(10005);
int vis[10005][15];
int dp[10005][15];
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int s, e;
    cin >> s >> e;
    for (int i = 0; i < m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].emplace_back(v,c);
        g[v].emplace_back(u,c);
    }
    priority_queue<pair<int,pair<int, int>>,vector<pair<int, pair<int, int>>>,greater<>> q;
    q.push({ 0,{s,0} });//距离 节点 使用多少次 k
    dp[s][0] = 0;
    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        int now = t.second.first;
        int usek = t.second.second;
        int dis = t.first;
        if (vis[now][usek])
        {
            continue;
        }
        vis[now][usek] = 1;
        for (auto & son : g[now])
        {
            int nt = son.first;
            int cost = son.second;
            if (dp[nt][usek] > dis + cost)
            {
                dp[nt][usek] = dis + cost;
                q.push({ dis + cost,{nt,usek } });
            }
            if (usek + 1 <= k && dp[nt][usek + 1] > dis)
            {
                dp[nt][usek + 1] = dis;
                q.push({ dis,{ nt,usek + 1 } });
            }
        }
    }
    int ans = 1e18;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans, dp[e][i]);
    }
    cout << ans << endl;
}
signed main()
{
    memset(dp, 0x3f, sizeof dp);
    //cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

P4822 [BJWC2012] 冻结 - 洛谷

思路：

注意操作，这里是将权值减半，其余不变

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,m,k;
//走到 i 用了 j 次
int dis[55][55];

vector<vector<pair<int,int>>> g(55);

void solve()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int u,v,t;
        cin >> u >> v >> t;
        g[u].emplace_back(v,t);
        g[v].emplace_back(u,t);
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            dis[i][j] = 1e18;
        }  
    }
    //时间 次数 点
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> pq;
    pq.push({0,0,1});
    while (!pq.empty())
    {
        auto [ut,uk,u] = pq.top();
        pq.pop();
        if(dis[u][uk] < ut || u == n)continue;
        for(auto & [v,w] : g[u])
        {
            if(dis[v][uk] > dis[u][uk] + w)
            {
                dis[v][uk] = dis[u][uk] + w;
                pq.push({dis[v][uk],uk,v});
            }
            if(uk < k && dis[v][uk+1] > dis[u][uk] + w / 2)
            {
                dis[v][uk+1] = dis[u][uk] + w / 2;
                pq.push({dis[v][uk+1],uk+1,v});                
            }
        }
    }
    int ans = 1e18;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans,dis[n][i]);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

AT_abc164_e [ABC164E] Two Currencies - 洛谷

思路：

本题特别注意，由于可以无限兑换，因此需要特判一下还要不要换，以及换了之后不能超过多少，同时不难看出我们所需的硬币最大数，以此优化内存确定上限

同时还有能不能走，如果不能走记得及时止损

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

struct MyStruct
{
    int to, cost, time;
};
vector<vector<MyStruct>> g(55);
vector<pair<int, int>> chage(55);
int n, m, s;
//到 i 城市还剩 j 枚银币
int dis[55][3505];
//int vis[55][3505];
void solve()
{
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++)
    {
        int u, v, x, t;
        cin >> u >> v >> x >> t;
        g[u].push_back({ v,x,t });
        g[v].push_back({ u,x,t });
    }
    for (int i = 1; i <= n; i++)
    {
        int c, d;
        cin >> c >> d;
        chage[i] = { c,d };
    }
    memset(dis, 0x3f, sizeof dis);
    int hascoin = min(2500LL, s);
    dis[1][hascoin] = 0;
    priority_queue<pair<pair<int,int>, int>, vector<pair<pair<int, int>, int>>, greater<>> pq;
    //耗时 银币 节点
    pq.push({ {0,hascoin}, 1});
    while (!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        int now = t.second;
        int costtime = t.first.first;
        int has = t.first.second;
        if (dis[now][has] < costtime)
        {
            continue;
        }
        //if (vis[now][has])
        //{
        //    continue;
        //}
        //vis[now][has] = 1;
        for (auto & son : g[now])
        {
            int shengxia = has - son.cost;
            if (shengxia < 0)
            {
                continue;
            }
            if (dis[son.to][shengxia] > dis[now][has] + son.time)
            {
                dis[son.to][shengxia] = dis[now][has] + son.time;
                pq.push({ {dis[now][has] + son.time,shengxia},son.to });
            }
        }
        int newcoin = min(has + chage[now].first,2500LL);
        if (dis[now][newcoin] > dis[now][has] + chage[now].second)
        {
            dis[now][newcoin] = dis[now][has] + chage[now].second;
            pq.push({ {dis[now][has] + chage[now].second,newcoin},now });
        }
    }
    for (int i = 2; i <= n; i++)
    {
        int ans = 1e18;
        for (int j = 0; j <= 2500; j++)
        {
            ans = min(ans, dis[i][j]);
        }
        cout << ans << endl;
    }
}
signed main()
{
    //cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

176. 装满的油箱 - AcWing题库

思路：

和上题差不多，属于可增加机会类型，贪心判断是否需要即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
int cost[1005];
vector<vector<pair<int, int>>> g(1005);
//从起点到 i 且剩下 j 油量的最小代价
int dp[1005][105];
int vis[1005][105];
struct Node
{
    int use, now, fuel;
    bool operator< (const Node& t) const //重载运算符，以d为优先级的小根堆
    {
        return use > t.use;
    }
};
int fuc(int c,int s,int e)
{
    memset(dp, 0x3f, sizeof dp);
    memset(vis, 0, sizeof vis); 
    dp[s][0] = 0;
    priority_queue<Node> pq;
    pq.push({0,s,0});
    while (!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        if (t.now == e)
        {
            return t.use;
        }
        //if (vis[t.now][t.fuel])
        //{
        //    continue;
        //}
        //vis[t.now][t.fuel] = 1;
        if (t.use > dp[t.now][t.fuel])
        {
            continue;
        }
        if (t.fuel < c && dp[t.now][t.fuel + 1] > t.use + cost[t.now])
        {
            dp[t.now][t.fuel + 1] = t.use + cost[t.now];
            pq.push({ t.use + cost[t.now] ,t.now,t.fuel + 1 });
        }
        for (auto & son : g[t.now])
        {
            if (t.fuel >= son.second && dp[son.first][t.fuel - son.second] > t.use)
            {
                dp[son.first][t.fuel - son.second] = t.use;
                pq.push({ t.use,son.first,t.fuel - son.second });
            }
        }
    }
    return -1;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)cin >> cost[i];
    for (int i = 0; i < m; i++)
    {
        int u, v, d;
        cin >> u >> v >> d;
        g[u].push_back({ v,d });
        g[v].push_back({ u,d });
    }
    int q;
    cin >> q;
    while (q--)
    {
        int C, S, E;
        cin >> C >> S >> E;
        int ans = fuc(C, S, E);
        if (ans == -1)
        {
            cout << "impossible\n";
        }
        else
        {
            cout << ans << endl;
        }
    }
}
signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

3200. 无线网络 - AcWing题库

思路：

模板，但是要自己建图，注意一下即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
vector<vector<int>> g(205);
vector<pair<int, int>> pos(205);
int n, m, k, r;
//到达 i 且多用了 j 个路由器的最小值
int dp[205][105];
struct Node
{
    int now,usek;
};

bool check(pair<int,int> p1,pair<int,int> p2)
{
    return (pow(p1.first - p2.first, 2) + pow(p1.second - p2.second,2)) <= r * r;
}

void fuc()
{
    queue<Node> pq;
    dp[0][0] = 0;
    pq.push({0,0});
    while (!pq.empty())
    {
        auto t = pq.front();
        pq.pop();
        if (t.now == 1)
        {
            continue;
        }
        for (auto& son : g[t.now])
        {
            int tempk = t.usek;
            if (son >= n)tempk++;
            if (tempk > k) continue;
            if (dp[son][tempk] > dp[t.now][t.usek] + 1)
            {
                dp[son][tempk] = dp[t.now][t.usek] + 1;
                pq.push({ son,tempk });
            }
        }
    }
}

void solve()
{
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> m >> k >> r;
    for (int i = 0; i < n+m; i++)
    {
        cin >> pos[i].first >> pos[i].second;
    }
    for (int i = 0; i < n+m; i++)
    {
        for (int j = 0; j < n+m; j++)
        {
            if (i == j) continue;
            if (check(pos[i], pos[j]))g[i].push_back(j);
        }
    }
    fuc();
    int ans = 1e9;
    for (int i = 0; i <= k; i++)
    {
        ans = min(dp[1][i], ans);
    }
    cout << ans-1 << endl;
}
signed main()
{
    //cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小雨坐地铁

思路：

特殊题型，这里我们是已经知道了有多少层，同时有无限次操作，因此需要改变

本题中我们使用到了另外一个技巧：虚点

我们可以选择构建分层图，但是如果层层间相互连接显然是一个 平方级别 的复杂度，我们显然不能接受

不妨考虑 n 个超级点源做 “虚层”，所有的点换线时我们做一个改变：先从 i 层 到 虚层，然后从虚层 到其余层，这样我们就变成了 线性级别的图

具体的，到 虚层 的权值为 0，而到其余层的权值就是 i 地铁站的 a[i]，对于同一层我们正常建图即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+1e3+7;
int n, m, s, e;
// 第几号线的 第几站 多少钱
vector<vector<tuple<int, int>>> g(N);
int dis[N];

void solve()
{
    fill(dis, dis + N, 1e18);
    cin >> n >> m >> s >> e;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int last, now;
        for (int j = 0; j < c; j++)
        {
            cin >> now;
            g[i * n + now].emplace_back(n * n + now, 0);
            g[n * n + now].emplace_back(i * n + now, a);
            if (j)
            {
                g[i * n + last].emplace_back(i * n + now, b);
                g[i * n + now].emplace_back(i * n + last, b);
            }
            last = now;
        }
    }
    s = n * n + s;
    e = n * n + e;
    dis[s] = 0;
    priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if (w > dis[u] || u == e)
            continue;
        for (auto &[v, cost] : g[u])
        {
            int newcost = w + cost;
            if (dis[v] > newcost)
            {
                dis[v] = newcost;
                pq.push({newcost, v});
            }
        }
    }
    if (dis[e] == 1e18)
    {
        cout << "-1\n";
        return;
    }
    cout << dis[e] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}