题目描述
约翰的农场有 $n$ 个谷仓,编号 $1 \sim n$,谷仓之间有 $m$ 条[HTML_REMOVED]双向[HTML_REMOVED]道路。
所有道路的长度均为 $1$。
奶牛们可以通过这些道路从任意谷仓到达任意其它谷仓。
任意两个谷仓之间最多只包含一条道路(注意是道路,不是路径)。
不存在道路两端都连接同一个谷仓的情况。
农场中一共有 $k$ 种干草,编号 $1 \sim k$。
每个谷仓都存有一种干草,其中第 $i$ 个谷仓存有第 $a_i$ 种干草。
每种干草都至少存在于一个谷仓中。
奶牛们计划选择一个谷仓举办干草宴会。
为了让宴会足够丰盛,至少需要将 $s$ 种不同的干草汇集在宴会谷仓。
宴会谷仓本身就包含一种干草,而其它干草就需要从其它谷仓运输。
已知,将一种干草从一个谷仓运至另一个谷仓所需的运输成本等于两谷仓之间的最短路径距离。
请你帮助奶牛们计算,对于每个谷仓,如果挑选其为宴会举办地,则举办宴会需要付出的总运输成本的最小可能值是多少。
输入格式
第一行包含四个整数 $n,m,k,s$。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。
接下来 $m$ 行,每行包含两个整数 $u,v$,表示第 $u$ 个谷仓和第 $v$ 个谷仓之间存在一条双向道路。
输出格式
共一行,输出 $n$ 个整数,其中第 $i$ 个整数表示在第 $i$ 个谷仓举办宴会需要付出的总运输成本的最小可能值。
数据范围
前 $3$ 个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n \le 10^5$,$0 \le m \le 10^5$,$1 \le s \le k \le \min(n,100)$,$1 \le a_i \le k$,$1 \le u,v \le n$,$u \neq v$。
输入样例1:
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
输出样例1:
2 2 2 2 3
输入样例2:
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
输出样例2:
1 1 1 2 2 1 1
算法思路
- 通过多源$BFS$,计算所有节点距离存储甘草编号为$k$的节点的最小距离,该距离用$dist[]$数组来维护,通过依次遍历所有的甘草编号,可以初始化$w[i][j]$,表示节点距离存储甘草$j$的最近距离,题目所求即为此数组$w[][]$,第二维上前$s$个数据的总和
- 该算法的优化一定程度上取决于排序取出前$s$个数据的快慢,题解$1$使用$sort()$库函数,题解$2$使用快排取数的库函数
$HINT$
- 原先记录每个节点存储甘草编号的数组$kd[N]$,数组的大小开辟成了$K$,始终评测结果为$WA$,纠结了一整天~
- 此处使用的是手写队列,调用库中的$queue$,会$TLE$
题解$1$
- 时间复杂度:$O(nk \log n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e+5 + 10, M = 2 * N, K = 105;
int n, m, k, s;
int h[N], e[M], ne[M], idx;
int w[N][K], dist[N];
int kd[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int id)
{
memset(dist, 0x3f, sizeof dist);
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++)
{
if (kd[i] == id)
{
dist[i] = 0;
q[++ tt] = i;
}
}
while (hh <= tt)
{
int u = q[hh ++];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[u] + 1)
{
dist[j] = dist[u] + 1;
q[++ tt] = j;
}
}
}
for (int i = 1; i <= n; i ++) w[i][id] = min(w[i][id], dist[i]);
}
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &s);
for (int i = 1; i <= n; i ++) scanf("%d", &kd[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
memset(w, 0x3f, sizeof w);
for (int i = 1; i <= k; i ++) bfs(i);
for (int i = 1; i <= n; i ++ )
{
sort(w[i] + 1, w[i] + k + 1);
int res = 0;
for (int j = 1; j <= s; j ++)
res += w[i][j];
printf("%d ", res);
}
return 0;
}
题解$2$
- 时间复杂度:$O(nk)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e+5 + 10, M = 2 * N, K = 105;
int n, m, k, s;
int h[N], e[M], ne[M], idx;
int w[N][K], dist[N];
int kd[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int id)
{
memset(dist, 0x3f, sizeof dist);
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++)
{
if (kd[i] == id)
{
dist[i] = 0;
q[++ tt] = i;
}
}
while (hh <= tt)
{
int u = q[hh ++];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[u] + 1)
{
dist[j] = dist[u] + 1;
q[++ tt] = j;
}
}
}
for (int i = 1; i <= n; i ++) w[i][id] = min(w[i][id], dist[i]);
}
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &s);
for (int i = 1; i <= n; i ++) scanf("%d", &kd[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
memset(w, 0x3f, sizeof w);
for (int i = 1; i <= k; i ++) bfs(i);
for (int i = 1; i <= n; i ++ )
{
nth_element(w[i] + 1, w[i] + s, w[i] + k + 1);
int res = 0;
for (int j = 1; j <= s; j ++)
res += w[i][j];
printf("%d ", res);
}
return 0;
}