首页 > 代码库 > BZOJ 1295 SCOI2009 最长距离 SPFA+暴力
BZOJ 1295 SCOI2009 最长距离 SPFA+暴力
题目大意:给定一个棋盘,一些格子上有障碍物,可以移除T个障碍物,求移除后所有能互相到达的点对中的最大欧几里得距离
m,n<=30,900个点,我们可以枚举起始点,跑一遍SPFA,求出所有经过不超过T个障碍物可达的点,统计ans即可
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 40 using namespace std; typedef pair<int,int> abcd; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; int n,m,T; double ans; char s[M]; int map[M][M]; abcd q[65540]; unsigned short r,h; bool v[M][M]; int f[M][M]; void SPFA(abcd x) { int i,j; memset(f,0x3f,sizeof f); q[++r]=x; f[x.first][x.second]=map[x.first][x.second]; while(r!=h) { abcd temp=q[++h]; v[temp.first][temp.second]=0; for(i=0;i<4;i++) { int xx=temp.first+dx[i]; int yy=temp.second+dy[i]; if(xx<=0||yy<=0||xx>m||yy>n) continue; if( f[xx][yy]>f[temp.first][temp.second]+map[xx][yy] && f[temp.first][temp.second]+map[xx][yy]<=T ) { f[xx][yy]=f[temp.first][temp.second]+map[xx][yy]; if(!v[xx][yy]) v[xx][yy]=1,q[++r]=make_pair(xx,yy); } } } for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(f[i][j]<=T) ans=max(ans,sqrt( (i-x.first)*(i-x.first) + (j-x.second)*(j-x.second) )); } int main() { int i,j; cin>>m>>n>>T; for(i=1;i<=m;i++) { scanf("%s",s+1); for(j=1;j<=n;j++) map[i][j]=s[j]-'0'; } for(i=1;i<=m;i++) for(j=1;j<=n;j++) SPFA(make_pair(i,j)); printf("%.6lf\n", ans ); }
BZOJ 1295 SCOI2009 最长距离 SPFA+暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。