天梯赛 登顶题解

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

using namespace std;
int n,m,l;
int k;
int a[62][130][1288];
int dir[3][3]={{0,0,-1},{-1,0,0},{0,-1,0}};
int father[9900000];
int num[9900000];
int find(int x)
{
    if(father[x]!=x)
         father[x]=find(father[x]);
  return father[x];
}
void join(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    {
        father[fx]=fy;
    }

}
int fun(int x,int y,int z)
{
    return n*m*(z-1)+m*(x-1)+y;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&l,&k);
    for(int i=1;i<=l;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=m;k++)
            {
                scanf("%d",&a[i][j][k]);
                if(a[i][j][k]==1)
                {father[fun(j,k,i)]=fun(j,k,i);}
            }
      
    for(int i=1;i<=l;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                for(int p=0;p<3;p++)
                {
                    if(a[i][j][k]==0)
                        continue;
                    int x=j+dir[p][0];
                    int y=k+dir[p][1];
                    int z=i+dir[p][2];
          if(a[z][x][y]==1)
           join(fun(j,k,i),fun(x,y,z));
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=l;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                
          num[find(fun(j,k,i))]++;
          
        
            }
        }
    }
    int len=fun(n,m,l);
    for(int i=1;i<=len;i++)
    {
        if(num[i]>=k)
           {
             
                ans+=num[i];
           }
    }
    printf("%d\n",ans);
    return 0;



}

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <string>
#include <strstream>

using namespace std;
typedef long long int LL;
const LL maxn=(LL)1<<62;
int n,m,k;
LL ds;
LL a[1020][1020];
LL d[1020];
int vis[1020];
map<string,int> m1;
double d1[20];
double d2[20];
int fun(string s)
{
    strstream ss;
    int num;
    ss << s;
    ss >> num;
    return num;
}
double Dijkstra(int x)
{
    for(int i=1;i<=n+m;i++)
        d[i]=maxn;
    memset(vis,0,sizeof(vis));
    d[x]=0;
    for(int i=1;i<=n+m;i++)
    {
        LL mm=maxn;
        int e=0;
        for(int j=1;j<=n+m;j++)
        {
            if(!vis[j]&&mm>d[j])
            {
                mm=d[j];
                e=j;
            }
        }
        vis[e]=1;
        for(int j=1;j<=n+m;j++)
        {
            if(!vis[j]&&d[j]>d[e]+a[e][j])
                d[j]=d[e]+a[e][j];
        }
    }
    LL sum=0;
    double sum2=1.0*d[1];
    for(int i=1;i<=n;i++)
    {
        if(d[i]>ds)
            return 0;
        sum+=d[i];
        sum2=min(sum2,1.0*d[i]);
    }

    d1[x-n]=1.0*sum/n;
    d2[x-n]=sum2;
    return sum2;
}
int main()
{
   scanf("%d%d%d%lld",&n,&m,&k,&ds);
   string x,y;LL z;
   int xx,yy;
   m1["G1"]=n+1;m1["G2"]=n+2;m1["G3"]=n+3;m1["G4"]=n+4;
   m1["G5"]=n+5;m1["G6"]=n+6;m1["G7"]=n+7;m1["G8"]=n+8;
   m1["G9"]=n+9;m1["G10"]=n+10;
   for(int i=1;i<=n+m;i++)
   {
       for(int j=1;j<=n+m;j++)
       {
           if(i==j)
                a[i][j]=0;
           else
                a[i][j]=maxn;
       }
   }
   for(int i=1;i<=k;i++)
   {
        cin>>x>>y>>z;
        if(x[0]<='9'&&x[0]>='0')
            xx=fun(x);
        else
            xx=m1[x];
        if(y[0]<='9'&&y[0]>='0')
            yy=fun(y);
        else
            yy=m1[y];
       a[xx][yy]=a[yy][xx]=min(a[xx][yy],z);
   }
   int ans=-1;double num=0;double num2=1.0*maxn;
   for(int i=n+1;i<=n+m;i++)
   {
       double nn=Dijkstra(i);
       if(nn!=0)
       {
            if(num<nn)
            {
                ans=i;
                num=nn;
                num2=d1[i-n];
            }
            else if(num==nn&&num2>d1[i-n])
            {
                ans=i;
                num=nn;
                num2=d1[i-n];
            }
       }
   }
   if(ans==-1)
        printf("No Solution\n");
   else
   {
       printf("G%d\n",ans-n);
       printf("%.1f %.1f\n",d2[ans-n],d1[ans-n]);
   }

   return 0;

}