题解 P1359 【租用游艇】

Hexarhy

2019-02-03 23:12:23

Solution

### 作为一道比较裸的图论题,解决方法当然不止一种,请诸君自行选择$\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$