题解 P2128 【赤壁之战】
lmrttx
2020-11-24 20:03:41
本题用 $DFS$ 解决。
先说下 $DFS$ 是什么吧。这就是搜索的一种,叫做深度优先搜索或者深搜。思想就是递归,判断何时退出搜索,以及回溯。回溯就是退回到某个过去的状态,重新开始搜索,这样更新答案的话答案正确性更高。
------------
接下来是更详细的介绍,如果已会自行跳过:
搜索是指对情况进行查找并且处理,如本题,我们就要把一艘艘船加进来处理。本题的处理是**通过情况更新最大值**。
这种搜索的思路是沿一个道路一直搜索,直到无路可走时,往回走,即回溯。我们由于有处理,所以可以从一个状态回到之前的状态。
图解,图片来源于百度。
![](https://p1.ssl.qhimgs1.com/sdr/400__/t017ed8533be81d6521.jpg)
![](https://p3.ssl.qhimgs1.com/sdr/400__/t01d9b359c58b1c695d.png)
从1号点开始搜索,一直走到6号点,这时无路可走了。回溯。一直到2号点。接着搜索5号点,然后到7号点。分别搜索4号点和8号点与9号点那一条路径。此时又回溯到5号点了。退回至1号点。
由于走过的点会被标记为走过,所以此时所有点的标记都是走过。无路可走时,便退出搜索,输出答案。
这个标记数组通常叫做 $vis$ 或 $visit$ 。
本题就是 $DFS$ 的框架,回溯与搜索于代码中理解。
$DFS$ 本身是递归,请先了解递归。
~~不用出门右转了,这边讲了。~~
递归就是在一个函数中直接或间接地调用到函数本身。但是一直调用,总要有返回的时候。于是要设置边界,符合边界条件时,层层返回。这一过程用栈在计算机内部实现。栈是一种**先进后出**的数据结构,一个表。
介绍完毕,见题目吧。
---------------------------------------------------------
题目分析:
发现是个搜索。看到
$"曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。"$
这句话时,就意识到是个点与点之间的 $DFS$ 了。搜索,判断是否返回,每次递归更新答案。
---------------------------------------------------------
注释和细节等见代码,让我们用代码分析这种搜索吧!
C++ CODE :
```cpp
#include<bits/stdc++.h>
using namespace std;
#define MAX 1001
int n,m,a[MAX][MAX],answer,v[MAX],boat[MAX];
bool vis[MAX];//vis为标记数组,表示是否搜索过编号为多少的船
void dfs(int ans,int x){//ans为当前最优的战略价值,x为在这一次搜索中,已经有了几艘船。
answer=max(answer,ans);//更新答案
if(x>n)return;//退出边界
for(register int i=1;i<=n;i++){
if(vis[i]==0){//还未访问
bool tag=true;//标记,这个标记指从当前一艘船向别的船搜索,还有没有连接的船,还能不能搜索下去。如果不能,退出,返回上一层。
for(int j=1;j<=x;j++)//循环,搜索的基础。
if(a[boat[j]][i]==0)//如果两艘船没有连接
{
tag=false;break;
//无路可走,标记更新为假
}
if(tag==true){
boat[x+1]=i;
vis[i]=true;
//每有一个新的搜索出发处,就要把这些东西处理一下。表示下一艘船是这艘,这艘被访问过了。
dfs(ans+v[i],x+1);
//递归搜索,总价值加上当前的价值,船的数量加1.
boat[x+1]=0;
vis[i]=false;
//回溯,回到搜索前的状态。
//因为我们的目标是让答案最优,所以回溯并不影响答案,只会让答案更加正确
}
}
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x][y]=666;//随便初始化为一个非0的数就可以了,因为为0时表示当前两艘船之间没有连接。
}
//搜索策略,从每艘船出发搜一遍
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));//由于每次都重新搜一遍,所以要清零
memset(boat,0,sizeof(boat));
//boat表示在这一次搜索中,第几艘船的编号为多少
vis[i]=true;
boat[1]=i;//初始化
dfs(v[i],1);
}
cout<<answer<<endl;
return 0;
}
```
作为一个基本 $DFS$,这题的练习意义还是很大的。蒟蒻最近在练习写题解,如有不足,可私聊提出。谢谢阅读,真心希望这篇题解对您有帮助!