深圳网站设计技术,珠宝网站建设要以商为本,阿里云WordPress一键安装,网站需要备案吗目录 引言一、道路与航线二、最优贸易三、选择最佳路线 引言
今天先是把之前还不熟的模板都写了一遍#xff0c;写了才能体会到#xff0c;其实模板写了背了其实还是不顶用#xff0c;还是要有大量的刷题积累#xff0c;才能把模板发挥出来#xff0c;不然真的你都看不出… 目录 引言一、道路与航线二、最优贸易三、选择最佳路线 引言
今天先是把之前还不熟的模板都写了一遍写了才能体会到其实模板写了背了其实还是不顶用还是要有大量的刷题积累才能把模板发挥出来不然真的你都看不出来模型你怎么去做。所以得大量的刷题啊加油吧 一、道路与航线
标签图论、SPFA、Dijkstra、最短路
思路这道题一看边权有负数所以第一时间就想着用 S P F A SPFA SPFA 算法了几乎就是模板然后过了 14 16 \frac{14}{16} 1614 的数据如果要是放在蓝桥杯里其实已经很不错了但要是为 A C M ACM ACM 赛制的话就等于没做所以我们就要对其优化。这里采用的是 S P F A S L E SPFA SLE SPFASLE 优化核心就是判断 d i s t [ j ] dist[j] dist[j] 和队头如果 d i s t [ j ] d i s t [ q . f r o n t ( ) ] dist[j]dist[q.front()] dist[j]dist[q.front()] 那就入队头否则入队尾。加这么点变化常数就会变小就刚好能过了。
题目描述
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T 个城镇编号为 1∼T。这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。每条道路 i 或者航线 i 连接城镇 Ai 到 Bi花费为 Ci。对于道路0≤Ci≤10,000;然而航线的花费很神奇花费 Ci 可能是负数(−10,000≤Ci≤10,000)。道路是双向的可以从 Ai 到 Bi也可以从 Bi 到 Ai花费都是 Ci。然而航线与之不同只可以从 Ai 到 Bi。事实上由于最近恐怖主义太嚣张为了社会和谐出台了一些政策保证如果有一条航线可以从 Ai 到 Bi那么保证不可能通
过一些道路和航线从 Bi 回到 Ai。由于约翰的奶牛世界公认十分给力他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。输入格式
第一行包含四个整数 T,R,P,S。接下来 R 行每行包含三个整数表示一个道路Ai,Bi,Ci。接下来 P 行每行包含三个整数表示一条航线Ai,Bi,Ci。输出格式
第 1..T 行第 i 行输出从 S 到达城镇 i 的最小花费如果不存在则输出 NO PATH。数据范围
1≤T≤25000,1≤R,P≤50000,1≤Ai,Bi,S≤T
输入样例
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
输出样例
NO PATH
NO PATH
5
0
-95
-100示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 3e410, M 5e4*310, INF 0x3f3f3f3f;int n, R, P, S;
int h[N], e[M], w[M], ne[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 spfa()
{memset(dist, 0x3f, sizeof dist);dist[S] 0; st[S] true;dequeint q; q.push_front(S);while(q.size()){int t q.front(); q.pop_front();st[t] false;for(int i h[t]; i ! -1; i ne[i]){int j e[i];if(dist[j] dist[t] w[i]){dist[j] dist[t] w[i];if(!st[j]) {if(q.size() dist[j] dist[q.front()]) q.push_front(j);else q.push_back(j);st[j] true;}}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1 , sizeof h);cin n R P S;while(R--){int a,b,c; cin a b c;add(a,b,c), add(b,a,c);}while(P--){int a, b, c; cin a b c;add(a,b,c);}spfa();for(int i 1; i n; i){if(dist[i] INF) cout NO PATH endl;else cout dist[i] endl;}return 0;
}二、最优贸易
标签图论SPFA
思路这道题刚开始我觉得就是找最大值和最小值一减就行了虽然过了几个样例但明显不对因为这是有路程顺序的并且不是所有的路都是双向的所以得模拟。我们可以用两个数组来记录当前结点及之前的点的最大值和最小值然后分别一正一反搜两次用 S P F A SPFA SPFA 算法因为有可能第一次走到的点不是最优的因为有可能退回来所以得用 S P F A SPFA SPFA剩余细节见代码。
题目描述
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 个正整数xyz每两个整数之间用一个空格隔开。如果 z1表示这条道路是城市 x 到城市 y 之间的单向道路如果 z2表示这条道路为城市 x 和城市 y 之间的双向道路。输出格式
一个整数表示答案。数据范围
1≤n≤100000,1≤m≤500000,1≤各城市水晶球价格≤100
输入样例
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例
5示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1e510, M 5e5*310, INF 0x3f3f3f3f;int n, m;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];void add(int h[], int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx;
}void spfa(int h[], int dist[], int S, bool type) //true为min
{memset(st, 0, sizeof st);if(type) memset(dist, 0x3f, sizeof dmax);else memset(dist, 0xcf, sizeof dmin);queueint q;dist[S] w[S], q.push(S), st[S] true;while(q.size()){int t q.front(); q.pop();st[t] false;for(int i h[t]; i ! -1; i ne[i]){int j e[i];if((type dist[j] min(dist[t], w[j])) || (!type dist[j] max(dist[t], w[j]))){if(type){dist[j] min(dist[t], w[j]);}else{dist[j] max(dist[t], w[j]);}if(!st[j]) {q.push(j);}}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);cin n m;for(int i 1; i n; i) cin w[i];while(m--){int u,v,t; cin u v t;add(h,u,v), add(rh,v,u);if(t 2) add(h,v,u), add(rh,u,v);}spfa(h, dmin, 1, true);spfa(rh, dmax, n, false);int res 0;for(int i 1; i n; i) {// cout dmax[i] dmin[i] endl;res max(res, dmax[i] - dmin[i]);}cout res endl;return 0;
}三、选择最佳路线
标签最短路
思路相当于给了一个图然后求任意多个点到一个点的最短路这里直接把边建成反向的然后从终点做一遍最短路然后在这多个起点中找最小值就行了。这里我把 S P F A SPFA SPFA 和 D i j k s t r a Dijkstra Dijkstra 算法都写了见代码自行查看。
题目描述
有一天琪琪想乘坐公交车去拜访她的一位朋友。由于琪琪非常容易晕车所以她想尽快到达朋友家。现在给定你一张城市交通路线图上面包含城市的公交站台以及公交线路的具体分布。已知城市中共包含 n 个车站编号1~n以及 m 条公交线路。每条公交线路都是 单向的从一个车站出发直接到达另一个车站两个车站之间可能存在多条公交线路。琪琪的朋友住在 s 号车站附近。琪琪可以在任何车站选择换乘其它公共汽车。请找出琪琪到达她的朋友家附近的公交车站需要花费的最少时间。输入格式
输入包含多组测试数据。每组测试数据第一行包含三个整数 n,m,s分别表示车站数量公交线路数量以及朋友家附近车站的编号。接下来 m 行每行包含三个整数 p,q,t表示存在一条线路从车站 p 到达车站 q用时为 t。接下来一行包含一个整数 w表示琪琪家附近共有 w 个车站她可以在这 w 个车站中选择一个车站作为始发站。再一行包含 w 个整数表示琪琪家附近的 w 个车站的编号。输出格式
每个测试数据输出一个整数作为结果表示所需花费的最少时间。如果无法达到朋友家的车站则输出 -1。每个结果占一行。数据范围
n≤1000,m≤20000,1≤s≤n,0wn,0t≤1000
输入样例
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
输出样例
1
-1示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010, M 2e510, INF 0x3f3f3f3f;int n, m, S, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int E[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(st, 0, sizeof st);
// memset(dist, 0x3f, sizeof dist);
// dist[S] 0; st[S] true;// queueint q; q.push(S);
// while(q.size())
// {
// int t q.front(); q.pop();
// st[t] false;// for(int i h[t]; i ! -1; i ne[i])
// {
// int j e[i];
// if(dist[j] dist[t] w[i])
// {
// dist[j] dist[t] w[i];
// if(!st[j]) st[j] true, q.push(j);
// }
// }
// }
// }void dijkstra()
{memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);dist[S] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0,S});while(heap.size()){auto t heap.top(); heap.pop();int v t.x, p t.y;if(st[p]) continue;st[p] true;for(int i h[p]; i ! -1; i ne[i]){int j e[i];if(dist[j] dist[p] w[i]){dist[j] dist[p] w[i];heap.push({dist[j],j});}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin n m S){memset(h, -1, sizeof h);while(m--){int a, b, c; cin a b c;add(b,a,c);}cin k;for(int i 0; i k; i){cin E[i];}dijkstra();
// spfa();int res INF;for(int i 0; i k; i){int j E[i];
// cout dist[j] ;res min(res, dist[j]);}if(res INF) cout -1 endl;else cout res endl;}return 0;
}
