Minimal Ratio Tree HDU - 2489

Minimal Ratio Tree HDU - 2489

暴力枚举点，然后跑最小生成树得到这些点时的最小边权之和。

由于枚举的时候本来就是按照字典序的，不需要额外判。

错误原因：要求输出的结尾不能有空格。

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 bool ok[],ok2[];

 bool vis[];

 int num,n,m;

 int a[],b[][];

 vector<int> vec;

 double anss;

 int dis[];

 void prim()

 {

     memset(vis,,sizeof(vis));

     memset(dis,0x3f,sizeof(dis));

     int i,j,s,sum=,mina,minid,s1=;

     for(s=;s<=n;s++)

         if(ok[s])

             break;

     vis[s]=;

     dis[s]=;

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

         if(ok[i])

             dis[i]=b[s][i];

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

     {

         mina=0x3f3f3f3f;

         minid=;

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

             if(ok[j]&&!vis[j]&&mina>dis[j])

             {

                 mina=dis[j];

                 minid=j;

             }

         sum+=mina;

         dis[minid]=;

         vis[minid]=;

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

             if(ok[j]&&!vis[j]&&dis[j]>b[minid][j])

                 dis[j]=b[minid][j];

     }

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

         if(ok[i])

             s1+=a[i];

     double tt=(double)sum/s1;

     if(tt<anss)

     {

         anss=tt;

         memcpy(ok2,ok,sizeof(ok));

     }

 }

 void dfs(int minn)

 {

     if(num>=m)

     {

         prim();

         return;

     }

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

         if(!ok[i])

         {

             ok[i]=;

             num++;

             dfs(i);

             ok[i]=;

             num--;

         }

 }

 int main()

 {

     int i,j;

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

     while(n!=&&m!=)

     {

         vec.clear();

         anss=;

         num=;

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

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

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

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

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

         dfs();

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

             if(ok2[i])

                 vec.push_back(i);

         for(i=;i<vec.size()-;i++)

             printf("%d ",vec[i]);

         printf("%d\n",vec[vec.size()-]);

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

     }

     return ;

 }