查询网站信息,跨境电商网址,scatter网站开发,天津网站建设 易尔通大多数都是同一个套路#xff0c;将图拆开成几个图#xff0c;每一层都对应着一个不同的状态#xff0c;比如把到点 i 的状态拆成经过了 j 次操作所得的 xx 结果#xff0c;一般数据不会很大
目前遇到的可分为 3 类#xff1a;
①.给你最多 k 次操作#xff0c;求 xx 结…大多数都是同一个套路将图拆开成几个图每一层都对应着一个不同的状态比如把到点 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];vectorvectorpairint,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_queuetupleint,int,int,vectortupleint,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][uk1] dis[u][uk]){dis[v][uk1] dis[u][uk];pq.push({dis[v][uk1],uk1,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];vectorvectorpairint,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_queuetupleint,int,int,vectortupleint,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][uk1] dis[u][uk]){dis[v][uk1] dis[u][uk];pq.push({dis[v][uk1],uk1,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
#includecstring
#include iomanip
#includecctype
#includestring
#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 endlvectorvectorpairint, 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_queuepairint,pairint, int,vectorpairint, pairint, 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];vectorvectorpairint,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_queuetupleint,int,int,vectortupleint,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][uk1] dis[u][uk] w / 2){dis[v][uk1] dis[u][uk] w / 2;pq.push({dis[v][uk1],uk1,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
#includecstring
#include iomanip
#includecctype
#includestring
#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;
};
vectorvectorMyStruct g(55);
vectorpairint, 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_queuepairpairint,int, int, vectorpairpairint, 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
#includecstring
#include iomanip
#includecctype
#includestring
#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];
vectorvectorpairint, 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_queueNode 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
#includecstring
#include iomanip
#includecctype
#includestring
#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
vectorvectorint g(205);
vectorpairint, int pos(205);
int n, m, k, r;
//到达 i 且多用了 j 个路由器的最小值
int dp[205][105];
struct Node
{int now,usek;
};bool check(pairint,int p1,pairint,int p2)
{return (pow(p1.first - p2.first, 2) pow(p1.second - p2.second,2)) r * r;
}void fuc()
{queueNode 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 nm; i){cin pos[i].first pos[i].second;}for (int i 0; i nm; i){for (int j 0; j nm; 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 1e61e37;
int n, m, s, e;
// 第几号线的 第几站 多少钱
vectorvectortupleint, 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_queuetupleint, int, vectortupleint, 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;
}
