洛谷：P1783 海滩防御（二分+并查集 最短路 最小生成树）

题意： 给定长度为N的海滩，然后有M做防御塔，给出每座塔的位置Xi，到海岸的距离Yi。 求防御塔上最小观测半径Ri，使得海滩被封锁。

思路：要使左边界和右边界连通。

很nice，可以二分+并查集做。 可以最小生成树做。 可以最短路做。

MST代码：

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

double x[maxn],y[maxn],ans; int tot,fa[maxn];

struct in{

    int u,v;

    double len;

}s[maxn];

bool cmp(in w,in p){return w.len<p.len;}

void add(int u,int v,double len)

{

    tot++; s[tot].u=u; s[tot].v=v; s[tot].len=len;

}

int find(int x){

    if(x==fa[x]) return x;

    return fa[x]=find(fa[x]);

}

int main()

{

    int N,M;

    scanf("%d%d",&N,&M);

    rep(i,,M) scanf("%lf%lf",&x[i],&y[i]);

    rep(i,,N+) fa[i]=i;

    rep(i,,M) add(,i,x[i]),add(N+,i,N-x[i]);

    rep(i,,M) rep(j,,M) add(i,j,0.5*sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));

    sort(s+,s+tot+,cmp);

    rep(i,,tot){

        int fu=find(s[i].u);

        int fv=find(s[i].v);

        if(fu==fv) continue;

        fa[fu]=fv;

        ans=s[i].len;

        if(find()==find(N+)) break;

    }

    printf("%.2lf\n",ans);

    return ;

}

最短路：把常规的路径求和改为路径最大值即可。代码：

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

double x[maxn],y[maxn],Len[maxn],ans,dis[maxn];

int cnt,Laxt[maxn],Next[maxn],To[maxn],N;bool vis[maxn];

void add(int u,int v,double l)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=l;

    Next[++cnt]=Laxt[v]; Laxt[v]=cnt; To[cnt]=u; Len[cnt]=l;

}

void SPFA()

{

    rep(i,,N+) dis[i]=0x3f3f3f3f;

    queue<int>q; q.push();

    while(!q.empty()){

        int u=q.front(); q.pop(); vis[u]=;

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i]; double t=max(dis[u],Len[i]);

            if(dis[v]>t){

                dis[v]=t;

                if(!vis[v]) q.push(v),vis[v]=;

            }

        }

    }

}

int main()

{

    int M;

    scanf("%d%d",&N,&M);

    rep(i,,M) scanf("%lf%lf",&x[i],&y[i]);

    rep(i,,M) add(,i,x[i]),add(N+,i,N-x[i]);

    rep(i,,M) rep(j,,M) add(i,j,0.5*sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));

    SPFA();

    printf("%.2lf\n",dis[N+]);

    return ;

}