bzoj1239

题解：

首先计算出两两之间的距离

然后二分答案

然后贪心判断是否可以放置少于等于k个

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,m,k,x,i,j,l,L,R,mid,r[N],d[N],h[N],dt[N][N];

int judge(int x)

{

    int temp=k,tot=m,t,u,v,c[N],p[N];

    for (int i=;i<n;i++)c[i]=h[i];

    for (int i=;i<n;i++)

     if (!c[i])

      {

        t=1e9;

        for (int j=;j<n;j++)

        if (c[j]==)t=min(t,dt[i][j]);

        if (t<=x)c[i]=,tot++;

      }

    if (tot==n)return ;

    while (temp--)

     {

        memset(p,,sizeof(p));

        for (int i=;i<n;i++)

         if (!c[i])

          for (int j=;j<n;j++)

           if (c[j]!=&&dt[i][j]<=x)p[j]++;

        u=;

        for (int i=;i<n;i++)

         if (c[i]!=&&p[i]>=u)u=p[i],v=i;

        if (!c[v])tot++;c[v]=;

        for (int i=;i<n;i++)

         if (!c[i])

          {

            t=1e9;

            for (int j=;j<n;j++)

             if (c[j]==)t=min(t,dt[i][j]);

            if (t<=x)c[i]=,tot++;

          }

        if (tot==n)return ;

     }

    return ;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for (int i=;i<n;i++)

     for (int j=;j<n;j++)dt[i][j]=(i==j)?:1e9;

    for (int i=;i<n;i++)scanf("%d",&r[i]);

    for (int i=;i<n;i++)

     {

        scanf("%d",&d[i]);

        R+=d[i];

        dt[i][r[i]]=dt[r[i]][i]=min(dt[i][r[i]],d[i]);

     }

    for (int i=;i<=m;i++)

     {

        scanf("%d",&x);

        h[x]=;

     }

    for (int l=;l<n;l++)

     for (int i=;i<n;i++)

      for (int j=;j<n;j++)

       if (i!=j&&i!=l&&j!=l)

        if (dt[i][l]+dt[l][j]<dt[i][j])dt[i][j]=dt[i][l]+dt[l][j];

    while (L<=R)

     {

        mid=(L+R)>>;

        if (judge(mid))R=mid-;

        else L=mid+;

     }

    printf("%d\n",L);

}