【圖論】分層圖 / 拆點

大多數都是同一個套路，將圖拆開成幾個圖，每一層都對應著一個不同的狀態，比如把到點 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" << endlvector<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} });//距離 節點 使用多少次 kdp[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" << endlstruct 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;
}