这题用到 枚举+prim

拍了半天队，已经没报希望了，wa了好多次，结果竟然ac，看自己做没错，一些细节没处理好。

总的来讲像这种数据小的题目用枚举完全无压力，放心用。

这里注意一下对于非重排列，就是说C多少的。

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std;
typedef long long lld;
typedef unsigned int ud;
#define Inf INT_MAX//int最大
#define Min(x,y) (x)<(y)?(x):(y)
#define Max(x,y) (x)>(y)?(x):(y)
#define PQ priority_queue
#define Q queue
#define N 20
int n,m;
double ans;
int map[N][N];
int w[N];
int mark[N];
int dis[N];
int mern;
int stack[N];
int res[N];double prim(int s)
{double edgeW=0;double vexW=0;for(int i=1;i<=m;i++){dis[stack[i]]=map[stack[s]][stack[i]];mark[stack[i]]=0;}dis[stack[s]]=0;mark[stack[s]]=1;vexW+=w[stack[s]];int t=m-1;while(t--){int min=Inf;int k;for(int i=1;i<=m;i++)if(!mark[stack[i]]&&dis[stack[i]]<min){min=dis[stack[i]];k=stack[i];}if(min==Inf)return Inf;mark[k]=1;edgeW+=dis[k];vexW+=w[k];for(int i=1;i<=m;i++)if(!mark[stack[i]]&&map[k][stack[i]]<dis[stack[i]])dis[stack[i]]=map[k][stack[i]];}return edgeW/vexW;
}void dfs(int nn)
{if(nn>m){double t=prim(1);if(t<ans){for(int i=1;i<nn;i++)res[i]=stack[i];ans=t;}return ;}if(stack[nn-1]+(m-nn)>n)return ;for(int i=stack[nn-1]+1;i<=n;i++){stack[nn]=i;dfs(nn+1);}
}int main()
{while(scanf("%d%d",&n,&m)&&(n||m)){for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);stack[0]=0;ans=(double)Inf;dfs(1);//printf("结果:");
        printf("%d",res[1]);for(int i=2;i<=m;i++)printf(" %d",res[i]);puts("");}return 0;
}