题目描述
作为城市的紧急救援团队负责人,你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市,道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时,你的工作是尽快带领你的士兵前往该地点,同时,在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N,表示城市数量(城市编号从 0 到 N−1),M 表示道路数量,C1 表示你当前所在的城市编号,C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数,其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行,每行包含三个整数 c1,c2,Li,表示城市 c1 和城市 c2 之间存在一条道路相连,道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。
输出格式
共一行,两个整数,第一个整数表示 C1 和 C2 之间最短路的数量,第二个整数表示走最短路的情况下,能聚集到的救援队最大数量。
数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。
【输入样例】
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
【输出样例】
2 4
算法1 SPFA $O(nm)$
单源最短路拓展,要求进行最短路的计数,在所有最短路中寻找一条点权和最大的路径,L2原题要求打印路径。
在SPFA最短路原有基础上需要维护几个新的数组:
nums 数组:当前节点处救援人员的数量;
cnt 数组:记录从起点到达当前节点有几条最短路径;
maxn数组:记录从起点到达当前节点可以召集多少救援人员;
使用spfa时候,有两个点一直过不去,debug深究才发现spfa的不合理性。
spfa求最短路时,被更新点并不具备最短路径的性质(而Dijkstra是具备的),这样在更新最短路径方案数时就很尴尬。
可以发现当dist[j] == dist[t] + W[i]时,若cnt[j] = cnt[j] + cnt[t];
会将这样冗余的路径一并计入(发生重复计数)。我们举一个反栗。
如上图,寻找从1到4的最短路径
从1出发,1入队,开始while循环:
- 1出队,更新2,3距离,将2、3入队,2、3的最短路径条数为1。
- 2出队,更新到4的最短距离,将4入队,4的最短路径条数为1。
- 3出队,此时dist[2] == dist[3] + w[3,2],更新2的最短路径条数为cnt[2] + cnt[3] = 1 + 1 = 2,发现2不在队内(上一步已出队),将2重新入队。
- 4出队,无路径更新。
- 2出队,dist[4] = dist[2] + w[2,4],更新2的最短路径条数为cnt[4] + cnt[2] = 2 + 1 = 3。
- 队列为空,结束while循环
然鹅可以发现4的最短路径只有两条,即(1->2->4)和(1->3->2->4)。
多记录了一条路径的原因是:有一条到2的最短路由于2的重复入队被重新计数了。
这是由于spfa的只要距离变小就会更新的性质导致的。
运行一下,发现与我们的分析一致。
线路的数量加等于:再算过cnt[j]之后,j的来源u点可能cnt继续增加,之前计算cnt[j]时没有被算到的路径数,用这种方法补全。
解决方法:新维护一个数组来记录上一次在这条路径的更新方案数,在这次更新时一个减去上回方案数。
C++ 代码(错误代码)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,start,en; // n是城市的个数,m是快速道路的条数,s是出发地的城市编号,d是目的地的城市编号
const int N = 610,M = N*2;
int h[N],W[M],e[M],ne[M],idx;
int nums[N]; // 每个城市的救援队的数目
int dist[N],cnt[N]; // dist[i]表示从起点到i的最短距离,cnt[i]表示从起点到i的最短路径的条数
int maxn[N]; // maxn[i]表示从起点到i能够召集的最多的救援队数量
int pre[N]; // 记录当前点的前驱节点
bool st[N]; // st[i]表示i是否已经在队列中
void add(int a,int b,int c)
{
W[idx] = c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0,cnt[start] = 1,maxn[start] = nums[start];
queue<int> q;
q.push(start); st[start] = true;
while(q.size() != 0)
{
auto 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]; //更新最短距离
cnt[j] = cnt[t]; //到达j的最短路径全部由t拓展而来
maxn[j] = maxn[t] + nums[j]; //召集j点的救援人员
pre[j] = t;
if(st[j] == false)
{
st[j] = true;
q.push(j);
}
}
// 最短路相等的时候,选能够获得救援最多的路
else if(dist[j] == dist[t] + W[i])
{
cnt[j] = cnt[j] + cnt[t]; //到达j的最短路径还可由t拓展而来
if(st[j] == false)
{
st[j] = true;
q.push(j);
}
//maxn[j] = max(maxn[j], maxn[t] + nums[j])
if(maxn[j] < maxn[t] + nums[j])
{
maxn[j] = maxn[t] + nums[j]; //更新最大能召集的救援人员
pre[j] = t; //更改前驱节点
}
}
}
}
}
/*
//递归找到起点,顺次输出路径
void print_path(int u)
{
if(u != start) print_path(pre[u]);
cout<<u<<' ';
}
*/
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>start>>en;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++) cin>>nums[i];
for(int i=0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<cnt[en]<<' '<<maxn[en]<<'\n';
//print_path(en);
return 0;
}
C++ 代码(ac代码)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,start,en; // n是城市的个数,m是快速道路的条数,s是出发地的城市编号,d是目的地的城市编号
const int N = 610,M = N*2;
int h[N],W[M],e[M],ne[M],idx;
int nums[N]; // 每个城市的救援队的数目
int dist[N],cnt[N]; // dist[i]表示从起点到i的最短距离,cnt[i]表示从起点到i的最短路径的条数
int maxn[N]; // maxn[i]表示从起点到i能够召集的最多的救援队数量
int pre[N]; // 记录当前点的前驱节点
bool st[N]; // st[i]表示i是否已经在队列中
int back[N][N]; //记录更新的方案数,便于减去
void add(int a,int b,int c)
{
W[idx] = c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0,cnt[start] = 1,maxn[start] = nums[start];
queue<int> q;
q.push(start); st[start] = true;
while(q.size() != 0)
{
auto 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]; //更新最短距离
cnt[j] = cnt[t]; //到达j的最短路径全部由t拓展而来
back[j][t] = cnt[j];
maxn[j] = maxn[t] + nums[j]; //召集j点的救援人员
pre[j] = t;
if(st[j] == false)
{
st[j] = true;
q.push(j);
}
}
// 最短路相等的时候,选能够获得救援最多的路
else if(dist[j] == dist[t] + W[i])
{
//cnt[j] = cnt[j] + cnt[t]; //到达j的最短路径还可由t拓展而来
cnt[j] = cnt[j] + cnt[t] - back[j][t]; //减去冗余的方案
back[j][t] = cnt[j]; //更新
if(maxn[j] < maxn[t] + nums[j])
{
maxn[j] = maxn[t] + nums[j]; //更新最大能召集的救援人员
pre[j] = t; //更改前驱节点
if(st[j] == false)
{
st[j] = true;
q.push(j);
}
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>start>>en;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++) cin>>nums[i];
for(int i=0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<cnt[en]<<' '<<maxn[en]<<'\n';
return 0;
}
算法2 堆优化版Dijkstra(ac代码) $O(mlogn)$
分析同上,在基础dijkstra算法上新维护几个数组即可。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,start,en; // n是城市的个数,m是快速道路的条数,s是出发地的城市编号,d是目的地的城市编号
const int N = 610,M = N*2;
int h[N],W[M],e[M],ne[M],idx;
int nums[N]; // 每个城市的救援队的数目
int dist[N],cnt[N]; // dist[i]表示从起点到i的最短距离,cnt[i]表示从起点到i的最短路径的条数
int maxn[N]; // maxn[i]表示从起点到i能够召集的最多的救援队数量
int pre[N]; // 记录当前点的前驱节点
bool st[N]; // st[i]表示i是否已经在队列中
void add(int a,int b,int c)
{
W[idx] = c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[start] = 0; cnt[start] = 1; maxn[start] = nums[start];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
heap.push({0,start});
while(heap.size() != 0)
{
auto ver = heap.top(); heap.pop();
int dis = ver.first, t = ver.second;
if(st[t] == true) continue; //是冗余备份
st[t] = true;
for(int i = h[t]; i!=-1; i =ne[i])
{
int j = e[i];
if(dist[j] > dis + W[i])
{
dist[j] = dis + W[i];
cnt[j] = cnt[t];
maxn[j] = maxn[t] + nums[j];
pre[j] = t;
heap.push({dist[j],j});
}
else if(dist[j] == dis + W[i])
{
cnt[j] = cnt[j] + cnt[t];
if(maxn[j] < maxn[t] + nums[j])
{
maxn[j] = maxn[t] + nums[j];
pre[j] = t;
}
}
}
}
}
/*
//递归找到起点,顺次输出路径
void print_path(int u)
{
if(u != start) print_path(pre[u]);
cout<<u<<' ';
}
*/
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>start>>en;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++) cin>>nums[i];
for(int i=0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dijkstra();
cout<<cnt[en]<<' '<<maxn[en]<<'\n';
//print_path(en);
return 0;
}
我宝贝好厉害呜呜呜
妈呀好辛苦
宝贝崴泥