引言
今天先是把之前还不熟的模板都写了一遍,写了才能体会到,其实模板写了背了其实还是不顶用,还是要有大量的刷题积累,才能把模板发挥出来,不然真的你都看不出来模型,你怎么去做。所以得大量的刷题啊,加油吧!
一、道路与航线
标签:图论、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 SPFA+SLE 优化,核心就是判断 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++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 3e4+10, M = 5e4*3+10, 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;
deque<int> 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 个正整数,x,y,z,每两个整数之间用一个空格隔开。
如果 z=1,表示这条道路是城市 x 到城市 y 之间的单向道路;如果 z=2,表示这条道路为城市 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++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1e5+10, M = 5e5*3+10, 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);
queue<int> 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,0<w<n,0<t≤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++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010, M = 2e5+10, 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;
// queue<int> 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_queue<PII, vector<PII>, greater<PII>> 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;
}