2020.6.25 C組灌

15513 ワード

問題を解く図説

この問題は最小生成ツリーを使う必要がある.
私たちはまずコストがC C Cより大きいパイプをマークします.最小生成ツリーをもう一度走ります.
注意:

点まで走ると、パイプの代価が積算されます.

全ての点を完走できなければ−1−1−1を出力する.

#include
#include
#include
#include
#include
#include
using namespace std;
int a[3010][3010],x[3010],y[3010],b[3010],c[3010];
int n,m,minn,k,ans;
int main()
{
    freopen("irrigation.in","r",stdin);
    freopen("irrigation.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
     for(int j=1; j<=n; j++)
      a[i][j]=999999999;  //      
    for(int i=1;i<=n;i++)
     {
        scanf("%d%d",&x[i],&y[i]);
        for(int j=1; j<=i-1; j++)   //     
         if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])>=m)
          a[i][j]=a[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
     }
    b[1]=1;
    for(int i=2; i<=n; i++)
     c[i]=a[1][i];
    for(int j=1; j<=n-1; j++)  //     
     {
         minn=999999998;  //minn   ，   999999999，      999999999
         for(int j=1; j<=n; j++)
         if(b[j]==0&&c[j]<=minn)
          {
            minn=c[j];
            k=j;
          }
         b[k]=1;
         ans+=c[k];    //  
         for(int j=1; j<=n; j++)
          if(b[j]==0&&a[j][k]<=c[j])
           c[j]=a[j][k];
     }
    for(int i=1; i<=n; i++)
     if(b[i]!=1)  //  
      {
        cout<<-1;
        return 0;
      }
    cout<<ans;
    return 0;
}

Angular 5学習ノート(一)

POJ 1201&&HDU 1384 Intervals(差分制約システム)