bzoj1239

题解：

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

然后二分答案

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

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50;
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=0;i<n;i++)c[i]=h[i];
    for (int i=0;i<n;i++)
     if (!c[i])
      {
        t=1e9;
        for (int j=0;j<n;j++)
        if (c[j]==1)t=min(t,dt[i][j]);
        if (t<=x)c[i]=2,tot++;
      }
    if (tot==n)return 1;
    while (temp--)
     {
        memset(p,0,sizeof(p));
        for (int i=0;i<n;i++)
         if (!c[i])
          for (int j=0;j<n;j++)
           if (c[j]!=1&&dt[i][j]<=x)p[j]++;
        u=0;
        for (int i=0;i<n;i++)
         if (c[i]!=1&&p[i]>=u)u=p[i],v=i;
        if (!c[v])tot++;c[v]=1;
        for (int i=0;i<n;i++)
         if (!c[i])
          {
            t=1e9;
            for (int j=0;j<n;j++)
             if (c[j]==1)t=min(t,dt[i][j]);
            if (t<=x)c[i]=2,tot++;
          }
        if (tot==n)return 1;
     }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=0;i<n;i++)
     for (int j=0;j<n;j++)dt[i][j]=(i==j)?0:1e9;
    for (int i=0;i<n;i++)scanf("%d",&r[i]);
    for (int i=0;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=1;i<=m;i++)
     {
        scanf("%d",&x);
        h[x]=1;
     }
    for (int l=0;l<n;l++)
     for (int i=0;i<n;i++)
      for (int j=0;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)>>1;
        if (judge(mid))R=mid-1;
        else L=mid+1;
     }
    printf("%d
",L);
}