题解 P1359 【租用游艇】
Hexarhy
2019-02-03 23:12:23
### 作为一道比较裸的图论题,解决方法当然不止一种,请诸君自行选择$\color{blue}\text{学习借鉴}$:
宣传[blog](https://80049.blog.luogu.org)……
> 注意:本题解程序码量较他人程序偏大,请做好心理准备。这不一定是最优解,只是为了拓宽大家的做题思路。
------------
$1)$最短路算法$+$松弛。由于数据较弱,可以使用$Floyd$、$spfa$、$dijkstra$、$Bellman-Ford$等最短路算法。**你没看错,$Floyd$也能过$QVQ$(参考他人题解)**
对于松弛操作,比较裸,类似$dp$,大家自己想吧(炒鸡简单滴)。
建图的话,邻接矩阵、普通邻接链表、链式前向星、$vector$存边等都可以,各式各样任君选择。
作者使用了~~通俗易懂~~的$spfa$+松弛+$vector$存边,参考下面程序。
~~时间复杂度玄学……~~
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int INF=0x7f7f7f7f;
const int MAXN=500;
int n;
struct node
{
int to,v;
};
vector <node> edge[MAXN];
queue <int> q;
int dis[MAXN];//此表示从1到i的最小花费
bool visit[MAXN];
void input(void)
{
cin>>n;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)//注意输入顺序!QAQ
{
int x;
cin>>x;
edge[i].push_back((node){j,x});//vecotr建图方便,不说
}
}
void spfa(void)
{
memset(dis,INF,sizeof(dis));//松弛前的准备
q.push(1);//起点入队
visit[1]=true;
dis[1]=0;
while(!q.empty())//按照流程来spfa
{
const int tmp=q.front();
for(vector<node>::iterator it=edge[tmp].begin();it!=edge[tmp].end();it++)
if(dis[it->to]>dis[tmp]+it->v)
{
dis[it->to]=dis[tmp]+it->v;//松弛
if(!visit[it->to])//入队标记
{
visit[it->to]=true;
q.push(it->to);
}
}
visit[tmp]=false;//spfa是要恢复标记哟
q.pop();
}
}
int main()
{
input();
spfa();
cout<<dis[n];//愉快的输出终点
return 0;
}
```
------------
$2)$拓扑排序$+dp$。(是不是有点少见?)
~~不会拓扑的同学出门左转度娘等你。~~
不过这里拓扑排序有点多余?好像题目已经保证前面节点一定是后面节点的前驱?这里略微提一下拓扑思路:
由于只能往下游走,那么我们可以拓扑求前驱节点,并更新$dis$数组的答案,(有点像松弛)。
可以保证的是拓扑排序也能遍历到每一条边(已经足够了),即使不像$spfa$反复遍历。
时间复杂度$O(N+E)$($N$为节点数、$E$为边的数量),已经算不错的。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int INF=0x7f7f7f7f;
const int MAXN=500;
int n;
struct node
{
int to,v;
};
vector <node> edge[MAXN];
int dis[MAXN],indeg[MAXN];//统计入度,拓扑的核心
bool visit[MAXN];
void input(void)
{
cin>>n;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
int x;
cin>>x;
indeg[j]++;//统计入度
edge[i].push_back((node){j,x});
}
}
void topo_sort(void)
{
memset(dis,INF,sizeof(dis));
queue <int> q;
for(int i=1;i<=n;i++)
if(!indeg[i]) //找到入度为0的起点(其实就是点1 QAQ)
{
q.push(i);
dis[i]=0;
}
while(!q.empty())//按照流程来拓扑
{
const int tmp=q.front();
q.pop();
for(vector<node>::iterator it=edge[tmp].begin();it!=edge[tmp].end();it++)
{
indeg[it->to]--;
if(!indeg[it->to])
q.push(it->to);
dis[it->to]=min(dis[it->to],dis[tmp]+it->v);//类似最短路松弛的dp
}
}
}
int main()
{
input();
topo_sort();
cout<<dis[n];
return 0;
}
```
------------
最后,对比一下上面两个程序的提交结果,没开$O2$:
![](https://cdn.luogu.com.cn/upload/pic/50932.png)
时间一样?$spfa$真玄学。
当然还有很多最短路的算法都能$AC$此题,时间复杂度各不相同,大家自行参考他人题解吧。
#### 完结撒花$QwQ$