题解 P1902 【刺杀大使】
P1902 刺杀大使
题目大意：
找出一条路径，使得从第 \(1\) 行到第 \(n\) 的上的最大值最小。
solution：
根据黑体字，很容易想到二分：
二分最大值，广搜验证。
细节处理：
- 广搜边界。
- 队列、标记初始化。
代码
#include
#include
#include
#include
using namespace std;
typedef pair PII;
const int N=1010;
int p[N][N];
int n,m;
int dx[10]={0,1,0,-1};
int dy[10]={1,0,-1,0};
queue q;
bool vis[N][N];
bool out(int x,int y){
if(x<1||x>n||y<1||y>m) return 1;
return 0;
}
bool check(int hurt){
memset(vis,0,sizeof(vis));
while(q.size()) q.pop();
q.push(make_pair(1,1));
vis[1][1]=1;
while(q.size()){
int x=q.front().first,y=q.front().second;q.pop();
if(x==n) return 1;
for(int z=0;z<4;z++){
int xx=x+dx[z],yy=y+dy[z];
if(out(xx,yy)) continue;
if(p[xx][yy]<=hurt&&!vis[xx][yy]){
q.push(make_pair(xx,yy));
vis[xx][yy]=1;
}
}
}
return 0;
}
int main(){
int l=0,r;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&p[i][j]);
r=max(r,p[i][j]);
}
}
while(l>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}
End
(但没完全End)
sulotion2:
考虑贪心做法，因为只与最大值有关，所以根据边权从小到大枚举边，加到并查集，最后判断连通性。
细节处理：
- 点与点之间的边权为点权取 \(\max\) 。
- 第一行与最后一行可缩为一点。
代码
咕了。