<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1127.香甜的黄油
农夫 $John$ 发现了做出全威斯康辛州最甜的黄油的方法:糖。
把糖放在一片牧场上,他知道 $N$ 只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。
当然,他将付出额外的费用在奶牛上。
农夫 $John$ 很狡猾,就像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。
他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
农夫 $John$ 知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。
给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。
数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式
第一行: 三个数:奶牛数 $N$,牧场数 $P$,牧场间道路数 $C$。
第二行到第 $N+1$ 行: $1$ 到 $N$ 头奶牛所在的牧场号。
第 $N+2$ 行到第 $N+C+1$ 行:每行有三个数:相连的牧场$A$、$B$,两牧场间距 $D$,当然,连接是双向的。
输出格式
共一行,输出奶牛必须行走的最小的距离和。
数据范围
$1 \le N \le 500$,
$2 \le P \le 800$,
$1 \le C \le 1450$,
$1 \le D \le 255$
这题用 $floyd$ 复杂度有危险($O(n ^ 3)$)
可以先枚举黄油的位置,再用 $dijkstra$ 求出每个牧场到当前位置的最短路。
复杂度为 $O(n ^ 2 log n)$,可以过(关于 spfa,它死了)
坑点一:
这道题不是每个牧场一个奶牛,一个牧场可能有好几个奶牛
于是,我们用 $cnt$ 数组来存第 $i$ 个仓库有几个奶牛
第 $i$ 个牧场的奶牛路程就是 $d_i \times cnt_i$
坑点二:
题目中说:数据保证至少存在一个牧场和所有牛所在的牧场连通
但是,没有奶牛的牧场虽然有可能贡献答案,也有可能不与有奶牛的牧场连通
所以枚举起点时要注意牧场之间的连通性(具体看代码)
c++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20009, INF = 1e9;
struct node
{//node存放边
int to, w;
//to表示路径终点,w表示路径权值
bool operator <(const node &x) const
{
if(w == x.w) return to > x.to;
else return w > x.w;
}
};
bool v[N];//记录节点有没有被访问
int d[N];//记录每一个节点到起点最短路
int cnt[N];//记录每个牧场有多少奶牛
int n;//奶牛个数
int p;//牧场个数
int m;//边的个数
int ans = INF;//答案
vector <node> vec[N];//存边
priority_queue <node> q;//优先队列
void dijkstra(int x)
{
for (int i = 1; i <= p; ++ i) d[i] = INF, v[i] = false;
//一开始,所有边都不与起点连通
d[x] = 0;//起点到自己的距离为0
q.push((node){x, 0});//起点入队
while (!q.empty())
{
node e = q.top(), tmp; q.pop();
v[e.to] = true;//这个点被方问过
for (int i = 0; i < vec[e.to].size(); ++ i)
{
tmp = vec[e.to][i];
if (v[tmp.to]) continue;
if (d[tmp.to] > d[e.to] + tmp.w)
{
d[tmp.to] = d[e.to] + tmp.w;//松弛
q.push((node) {tmp.to, d[tmp.to]});//入优先队列
}
}
}
return;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> p >> m;
while (n --)
{
int cow; cin >> cow;
cnt[cow] ++;
}
for (int i = 1, u, v, w; i <= m; ++ i)
{//u代表路径起点,v代表路径终点,w代表路径长度
cin >> u >> v >> w;
vec[u].push_back((node) {v, w});//建边
vec[v].push_back((node) {u, w});//建反边
//因为是无向图,建两条边
}
for(int i = 1, sum;i <= p;++ i)
{
dijkstra(i); sum = 0;
bool flag = true;//判断奶牛是否都能走到点 i
for (int j = 1; j <= p; ++ j)
if(cnt[j])//如果有奶牛
{
if (d[j] == INF)//如果有奶牛走不到牧场i
{
flag = false;//一定不是答案
break;
}
sum += cnt[j] * d[j];//累加答案
}
if (flag) ans = min(ans, sum);
}
cout << ans << endl;
return 0;
}
应该是mnlogn吧
没有m你走错了吧
迪杰斯特拉复杂度确实是mnlogn
实测spfa能过啊
运算符重载里面不应该是w<x.w吗