BZOJ1295: [SCOI2009]最长距离【最短路】

数据范围≤30、、哈哈这么小啊、、

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

由于数据范围小的出奇那么可以大胆考虑对每个点做一次spfa、连边这样连：(u,v)如果v是障碍那么连的边权就是1、否则连0、每个点都向上下左右各连一条边、接下来跑spfa、要注意一点：如果以一个障碍点为源点开始spfa、那么t要先减一、因为首先得把这个位置上的障碍移掉、然后跑出来每个点的距离就是要移开的障碍数、小于等于T就更新答案即可、

 

?
BZOJ1295
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define pos(x,y) (((x)-1)*m+(y))
int p[10000],w[10000],n1[10000],h[1000],d[1000],q[500000],v[1000],a[40][40],tot=0,n,m,t,An=0;
char s[40]; int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
inline void ae(int a,int b,int c){
    p[tot]=b;   w[tot]=c;   n1[tot]=h[a];  h[a]=tot++;
}inline void spfa(int S){
    memset(d,63,sizeof(d)); memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=S; v[S]=1; d[S]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i]){
            if(d[p[i]]>d[u]+w[i]){
                d[p[i]]=d[u]+w[i];
                if(!v[p[i]])    q[tail++]=p[i], v[p[i]]=1;
            }
        }
    }
}inline void build(){
    memset(h,0xff,sizeof(h));
    for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++){
        for(int k=0;k<4;k++){
            int xx=i+dx[k],yy=j+dy[k];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m)  ae(pos(i,j),pos(xx,yy),a[xx][yy]);
        }
    }
}int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)   a[i][j]=s[j]-'0';
    }build();
    for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++){
        spfa(pos(i,j)); t-=a[i][j];
        for(int u=1;u<=n;u++)   for(int v=1;v<=m;v++)
            if(d[pos(u,v)]<=t)  An=max(An,(u-i)*(u-i)+(v-j)*(v-j));
        t+=a[i][j];
    }printf("%.6lf\n",sqrt((double)An));
    return 0;
}

BZOJ BZOJ spfa Comments(0) 2013年6月07日 13:59