HDU - 2489（枚举+最小生成树）

通过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;
}