首页 > 代码库 > 【spfa】bzoj1295 [SCOI2009]最长距离

【spfa】bzoj1295 [SCOI2009]最长距离

2024-07-25 03:01:34   218人阅读

题意：给你一个n*m的点阵、有些点是障碍，求一个欧几里得距离最大的点对(A,B)，使得在移走的障碍≤T的情况下，可以从A走到B。

建图，跑n*m次spfa，求出从 每个点 出发到 其他所有点 的 经过的障碍数。若这个值<=T，则可以用来更新答案。

 1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 8 queue<int>q; 9 char map[31][31];10 int n,en,m,K,first[50001],next[50001],v[50001],w[50001],dis[50001],num[31][31];11 bool inq[50001];12 double ans;13 void init(const int &s)14 {memset(dis,0x7f,sizeof(dis)); inq[s]=true; dis[s]=0; q.push(s);}15 void AddEdge(const int &U,const int &V,const int &W)16 {v[++en]=V; w[en]=W; next[en]=first[U]; first[U]=en;}17 int sqr(const int &x){return x*x;}18 double Euclid_Dis(const int &x1,const int &y1,const int &x2,const int &y2)19 {return sqrt(sqr(x1-x2)+sqr(y1-y2));}20 void spfa(const int &s)21 {22     init(s);23     while(!q.empty())24       {25           int cur=q.front();26           for(int i=first[cur];i;i=next[i])27             if(dis[v[i]]>dis[cur]+w[i])28               {29                 dis[v[i]]=dis[cur]+w[i];30                 if(!inq[v[i]])31                   {32                     q.push(v[i]);33                     inq[v[i]]=true;34                   }35               }36           q.pop(); inq[cur]=false;37       }38 }39 void calc(const int &x,const int &y)40 {41     K-=(map[x][y]==‘1‘);42     for(int i=0;i<n;i++)43       for(int j=0;j<m;j++)44         if(dis[num[i][j]]<=K)45           ans=max(ans,Euclid_Dis(x,y,i,j));46     K+=(map[x][y]==‘1‘);47 }48 void BuildGraph()49 {50     for(int i=0;i<n;i++)51       for(int j=0;j<m;j++)52         for(int k=0;k<4;k++)53           {54             int tx=i+dx[k],ty=j+dy[k];55             if(tx>=0&&tx<n&&ty>=0&&ty<n)56               if(map[tx][ty]==‘1‘) AddEdge(num[i][j],num[tx][ty],1);57               else AddEdge(num[i][j],num[tx][ty],0);58           }59 }60 int main()61 {62     scanf("%d%d%d",&n,&m,&K);63     for(int i=0;i<n;i++)64       scanf("%s",map[i]);65     for(int i=0;i<n;i++)66       for(int j=0;j<m;j++)67         num[i][j]=++en;68     en=0;69     BuildGraph();70     for(int i=0;i<n;i++)71       for(int j=0;j<m;j++)72         {73           spfa(num[i][j]);74           calc(i,j);75         }76     printf("%.6lf\n",ans);77     return 0;78 }

 

【spfa】bzoj1295 [SCOI2009]最长距离


联系
我们