通过dfs枚举所有点集合的情况,然后对这些点进行prim求的最小生成树。
然后将边权和点权的比以及点集合存在到一个结构体数组里面,然后先对边权和点权的比进行排序,
如果相等的话就按点集合的字典序排序即可;
代码如下:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 20;
struct node
{
double num;
int data[20], len;
};
int data[N], res[N], map[N][N], father[N], sum[N], ans_len = 1;
node ans_data[100000];
int n, m;
void init()
{
for (int i = 1; i <= n; i++)
{
father[i] = i;
sum[i] = 1;
}
}
int find(int x)
{
if(x != father[x])
{
father[x] = find(father[x]);
}
return father[x];
}
int merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx != fy)
{
father[fx] = fy;
sum[fy] += sum[fx];
return sum[fy];
}
return -1;
}
double judge(int len, int a)
{
int sum = 0;
int lowcost[N], min = 99999999;
lowcost[res[1]] = 0;
for (int i = 2; i <= len; i++)
{
lowcost[res[i]] = map[res[1]][res[i]];
}
for (int i = 2; i <= len; i++)
{
min = 99999999;
int u = 0;
for (int j = 1; j <= len; j++)if(lowcost[res[j]] != 0 && min > lowcost[res[j]])
{
u = j;
min = lowcost[res[j]];
}
lowcost[res[u]] = 0;
sum += min;
for (int j = 1; j <= len; j++)if(lowcost[res[j]] != 0 && map[res[u]][res[j]] < lowcost[res[j]])
{
lowcost[res[j]] = map[res[u]][res[j]];
}
}
return (sum * 1.0) / (a * 1.0);
}
bool cmp0(node a, node b)
{
int len = min(a.len, b.len);
int i = 1, j = 1;
while(i <= len && j <= len)
{
if(a.data[i] < b.data[j])
{
return true;
}
else if(a.data[i] > b.data[j])
{
return false;
}
else if(a.data[i] == b.data[j])
{
i++;
j++;
}
}
return a.len < b.len;
}
bool cmp(node a,node b)
{
return a.num == b.num ? cmp0 (a,b): a.num < b.num;
}
void dfs(int len, int index,int sum)
{
if (index == m + 1)
{
init();
double ans = judge(index - 1, sum);
if(ans != -1)
{
for (int i = 1; i <= index - 1; i++)
{
ans_data[ans_len].data[i] = res[i];
}
ans_data[ans_len].len = index - 1;
ans_data[ans_len].num = ans;
ans_len++;
}
}
else
{
for (int i = len; i <= n; i++)
{
res[index] = i;
dfs(i+1,index + 1,sum + data[i]);
}
}
}
/*
3 2
30 20 10
0 6 2
6 0 3
2 3 0
2 2
1 1
0 2
2 0
0 0
Sample Output
1 3
1 2
5 3
10 51 31 10 10
0 15 61 3 41
15 0 4 4 5
61 4 0 4 9
3 4 4 0 4
41 5 9 4 0
2 3 4
*/
int main()
{
while(scanf("%d %d",&n, &m) && (n != 0 && m != 0))
{
ans_len = 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", &data[i]);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
scanf("%d", &map[i][j]);
}
}
dfs(1,1,0);
sort(ans_data + 1, ans_data + ans_len, cmp);
for (int i = 1; i <= ans_data[1].len; i++)
{
if(i < ans_data[1].len)
{
printf("%d ", ans_data[1].data[i]);
}
else
{
printf("%d", ans_data[1].data[i]);
}
}
printf("\n");
}
return 0;
}