Acwing 1135 新年好
重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e
过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。
怎样走，才需要最少的时间？
输入格式
第一行：包含两个整数 n,m 分别表示车站数目和公路数目。
第二行：包含五个整数 a,b,c,d,e 分别表示五个亲戚所在车站编号。
以下 m 行，每行三个整数 x,y,t 表示公路连接的两个车站编号和时间。
输出格式
输出仅一行，包含一个整数 T，表示最少的总时间。
数据范围
思路
本题会卡掉spfa 所以用堆优化的Dijkstra做
先预处理 每个点到其他点的最短距离
再dfs暴力枚举访问的顺序 取最小值
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 500010, INF = 0x3f3f3f3f; int n, m; int dist[6][N]; int source[6]; bool st[N]; vector<pair<int, int>>vec[N]; void dijkstra(int start, int dist[]) { memset(dist, 0x3f, N * 4); dist[start] = 0; memset(st, false, sizeof st); priority_queue<PII, vector<PII>, greater<PII>>heap; heap.push({ 0,start }); while (!heap.empty()) { auto t = heap.top(); heap.pop(); int ver = t.second; if (st[ver])continue; st[ver] = true; for (int i = 0; i < vec[ver].size(); ++i) { int j = vec[ver][i].second; int w = vec[ver][i].first; if (dist[j] > dist[ver] + w) { dist[j] = dist[ver] + w; heap.push({ dist[j],j }); } } } } int dfs(int u, int start, int distance) { if (u == 6)return distance; int res = 0x3f3f3f3f; for (int i = 1; i <= 5; ++i) { int next_ = source[i]; //下一个点的编号 if (!st[i]) { st[i] = true; res = min(res, dfs(u + 1, i, distance + dist[start][next_])); st[i] = false; } } return res; } int main() { cin >> n >> m; source[0] = 1; for (int i = 1; i <= 5; ++i)scanf("%d", &source[i]); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); vec[u].push_back({ w,v }); vec[v].push_back({ w,u }); } for (int i = 0; i < 6; ++i) { dijkstra(source[i], dist[i]); } memset(st, false, sizeof st); printf("%d\n", dfs(1, 0, 0)); return 0; }
AcWing 340. 通信线路
在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站A i 和B i
特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。
现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费L i
电话公司正在举行优惠活动。
农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
输入格式
第1行：三个整数N，P，K。
第2…P+1行：第 i+1 行包含三个整数A i , B i , L i
输出格式
包含一个整数表示最少花费。
若1号基站与N号基站之间不存在路径，则输出”-1”。
数据范围
0≤K<N≤1000
1≤P≤10000
1≤Li≤1000000
思路
题意为求一条从1-n的路径上的第k+1大的边的权值的最小值
因为是求最大值的最小值 可以想到用二分做
二分第k+1大的边的权值 然后把 大于这条边的边权值设置为1 小于这条边的边权值设置为0
整个图中只有权值为0/1的边 所以可以用双端队列广搜做
当dist[n]>k时 说明mid的值偏小
当dist[n]<=k时 说明mid的值可能为答案或者偏大
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 1010; int n, m, k; vector<PII>vec[N]; deque<int>q; bool st[N]; int dist[N]; bool check(int bound) { memset(st, false, sizeof st); memset(dist, 0x3f, sizeof dist); q.push_back(1); dist[1] = 0; while (!q.empty()) { auto t = q.front(); q.pop_front(); if (st[t])continue; st[t] = true; for(int i = 0 ;i < vec[t].size();++i){ int j = vec[t][i].second; int v = vec[t][i].first > bound; if (dist[j] > dist[t] + v) { dist[j] = dist[t] + v; if (!v) q.push_front(j); else q.push_back(j); } } } return dist[n] <= k; } int main() { cin >> n >> m >> k; while (m--) { int u, v, w; cin >> u >> v >> w; vec[u].push_back({ w,v }); vec[v].push_back({ w,u }); } int l = 0, r = 1e6 + 1; while (l < r) { int mid = l + r >> 1; if (check(mid))r = mid; else l = mid + 1; } if (r == 1e6 + 1)r = -1; cout << r << endl; return 0; }
AcWing 342. 道路与航线
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。
他想把牛奶送到T个城镇，编号为1~T。
这些城镇之间通过R条道路 (编号为1到R) 和P条航线 (编号为1到P) 连接。
每条道路 i 或者航线 i 连接城镇A i到B i ，花费为C i
对于道路，0 ≤ C i ≤ 10 , 000 ;然而航线的花费很神奇，花费Ci可能是负数(− 10 , 000 ≤ C i ≤ 10 , 000 )。
道路是双向的，可以从A i到B i ，也可以从B i到A i ，花费都是C i 然而航线与之不同，只可以从A i 到B i
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从A i 到B i ，那么保证不可能通过一些道路和航线从B i 回到A i
由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇S把奶牛送到每个城镇的最便宜的方案。
输入格式
第一行包含四个整数T,R,P,S。
接下来R行，每行包含三个整数（表示一个道路）A i , B i , C i
接下来P行，每行包含三个整数（表示一条航线）A i , B i , C i
输出格式
第1…T行：第 i 行输出从 S 到达城镇 i 的最小花费，如果不存在，则输出“NO PATH”。
数据范围
1 ≤ T ≤ 25000
1 ≤ R , P ≤ 50000
1 ≤ A i , B i , S ≤ T
思路
dijkstra+topsort
没有负权边的图可以用Dijkstra 有向无环图不管边权正负都可以用SPFA
1.先输入所有双向道路 dfs出所有连通块 计算两个数组：id[]存储每个点属于哪个连通块；$vectorblock[] $存储每个连通块里有哪些点；
2.输入所有航线，同时统计出每个连通块的入度
3.按照拓扑序依次处理每个连通块。先将所有入度为0的连通块的编号加入队列中
4.每次从队头取出一个连通块的编号bid
5.将该]block[bid]中的所有点加入堆中，然后对堆中所有点跑Dijkstra算法
6.每次取出堆中距离最小的点的ver
7.然后遍历ver的所有邻点j jj。如果id[ver]==id[j]那么如果j能被更新 将j插入堆中；如果 id[ver] != id[j]
则将]id[j] 这个连通块的入度减1，如果减成0了，则将其插入拓扑排序的队列中
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 25010; int n, mr, mp, S; int id[N], dist[N], din[N]; vector<int>block[N]; vector<PII>vec[N]; bool st[N]; int bcnt; queue<int>q; void dijkstra(int bid) { priority_queue<PII, vector<PII>, greater<PII>>heap; for (int i = 0; i < block[bid].size(); ++i) { int j = block[bid][i]; heap.push({ dist[j],j }); } while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second; if (st[ver])continue; st[ver] = true; for (int i = 0; i < vec[ver].size(); ++i) { int j = vec[ver][i].second; int dis = vec[ver][i].first; if (dist[j] > dist[ver] + dis) { dist[j] = dist[ver] + dis; if (id[j] == id[ver])heap.push({ dist[j],j }); } if (id[j] != id[ver] && --din[id[j]] == 0)q.push(id[j]); } } } void topsort() { memset(dist, 0x3f, sizeof dist); dist[S] = 0; for (int i = 1; i <= bcnt; ++i) { if (!din[i]) q.push(i); } while (q.size()) { int t = q.front(); q.pop(); dijkstra(t); } } void dfs(int u, int bid) { id[u] = bid; block[bid].push_back(u); for (int i = 0; i < vec[u].size(); ++i) { int j = vec[u][i].second; if (!id[j]) dfs(j, bid); } } int main() { cin >> n >> mr >> mp >> S; while (mr--) { int u, v, w; cin >> u >> v >> w; vec[u].push_back({ w,v }); vec[v].push_back({ w,u }); } for (int i = 1; i <= n; ++i) { if (!id[i]) dfs(i, ++bcnt); } while (mp--) { int u, v, w; cin >> u >> v >> w; vec[u].push_back({ w,v }); din[id[v]]++; } topsort(); for (int i = 1; i <= n; ++i) { if (dist[i] > INF / 2)puts("NO PATH"); else printf("%d\n", dist[i]); } return 0; }
AcWing 341 最优贸易
C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。
任意两个城市之间最多只有一条道路直接相连。
这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。
C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。
但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到C国旅游。
当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。
设C国 n 个城市的标号从 1~n，阿龙决定从1号城市出发，并最终在 n 号城市结束自己的旅行。
在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。
阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。
请你告诉阿龙，他最多能赚取多少旅费。
注意：本题数据有加强。
输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。
如果z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。
输出格式
一个整数，表示答案。
数据范围
1≤n≤100000
1≤m≤500000
1≤各城市水晶球价格≤100
思路
dmin[k] 表示1−k 价格的最小值dmax[k] 表示 k−n 价格的最大值
SPFA求出dmin和dmax后 遍历1−n 求出dmax[k]−dmin[k] 的最大值
在求dmin和dmax时 需要建反图
用Dijkstra会超时 所以用SPFA
代码
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n, m; int w[N]; int dmin[N], dmax[N]; vector<int>vec1[N]; vector<int>vec2[N]; queue<int>q; bool st[N]; void spfa(vector<int>vec[], int dist[], int type) { if (type == 0) { memset(dist, 0x3f, sizeof dmin); dist[1] = w[1]; q.push(1); } else { memset(dist, 0, sizeof dmax); dist[n] = w[n]; q.push(n); } while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = 0; i < vec[t].size(); ++i) { int j = vec[t][i]; if ((type == 0 && dist[j] > min(dist[t], w[j])) || (type == 1 && dist[j] < max(dist[t], w[j]))) { if (type == 0) dist[j] = min(dist[t], w[j]); else dist[j] = max(dist[t], w[j]); if (!st[j]) { q.push(j); st[j] = true; } } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i)scanf("%d", &w[i]); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); vec1[u].push_back(v); vec2[v].push_back(u); if (w == 2) { vec1[v].push_back(u); vec2[u].push_back(v); } } spfa(vec1, dmin, 0); spfa(vec2, dmax, 1); int res = -1; for (int i = 1; i <= n; ++i) { res = max(res, dmax[i] - dmin[i]); } cout << res << endl; return 0; }
