当前位置: 代码迷 >> 综合 >> P1828 [USACO3.2]香甜的黄油 Sweet Butter 题解
  详细解决方案

P1828 [USACO3.2]香甜的黄油 Sweet Butter 题解

热度:80   发布时间:2024-01-29 16:26:11.0

博客园同步

原题链接

简要题意:

给定一个 n n 个点的无向图,有边权。有 k k 个仓库,每个点属于一个仓库。

你需要选定 k k 个仓库其中的一个使得所有点到它的最短路上的边权之和最小。求这个最小的和。

n 800 n \leq 800 .

一看到 n 800 n \leq 800 ,算法很明显。有两种解决方案。

算法一

利用 Floyd \text{Floyd} .

可以用 O ( n 3 ) \mathcal{O}(n^3) 的时间求出两两最短路。

下面大力统计即可。

时间复杂度: O ( n 3 ) \mathcal{O}(n^3) .

实际得分: 0 p t 0pt .

算法二

利用 SPFA \text{SPFA} $.

同样是求两两点最短,考虑 n n 次单源,用 SPFA \text{SPFA} 做到 O ( n 3 ) \mathcal{O}(n^3) .

实际上这东西跑不满。

时间复杂度: O ( n 3 ) \mathcal{O}(n^3) .

实际得分: 100 p t s 100pts .(不可能跑满啊)

#include<bits/stdc++.h>
using namespace std;inline int read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-')f=-f; ch=getchar();}int x=0;while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}int n,p,c;
vector<pair<int,int> >G[2001];
int dis[2001],vis[2001],a[2001];inline int SPFA(int stc) { //SPFA 单源求出所有点到 stc 的最短路queue<int>q;memset(dis,0x3f,sizeof(dis)); dis[stc]=0; vis[stc]=1;q.push(stc);while(!q.empty()) {int u=q.front(); q.pop(); vis[u]=0;for(int i=0;i<G[u].size();i++) {int v=G[u][i].first,c=G[u][i].second;if(dis[v]>dis[u]+c) {dis[v]=dis[u]+c;if(!vis[v]) {vis[v]=1; q.push(v);}}}}int s=0;for(int i=1;i<=n;i++) s+=dis[a[i]];return s; //统计当前仓库的答案
}int main(){n=read(),p=read(),c=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=c;i++) {int u=read(),v=read(),w=read();G[u].push_back(make_pair(v,w));G[v].push_back(make_pair(u,w));}int mini=INT_MAX;for(int i=1;i<=p;i++) mini=min(mini,SPFA(i));printf("%d\n",mini); //最小答案return 0;
}

算法三

考虑数据加强: n 2000 n \leq 2000 .

同样求两两最短路,用 n n Dijkstra \text{Dijkstra} 即可做到 O ( n 2 log ? n ) \mathcal{O}(n^2 \log n) .

时间复杂度: O ( n 2 log ? n ) \mathcal{O}(n^2 \log n) .

实际得分: 100 p t s 100pts .