[POJ][3925][深搜+最小生成树] Minimal Ratio Tree

题目大意：

给出一个图，要求在图中选取一些节点和边构成一个“边权和/点权和”最小的树。

思路：

用深搜从遍历所有m个点的选择方案，方案一旦确定，点权值也被确定。然后用最小生成树计算边权值。建立一个数组tree[]记录结果，将当前最小比值的选择方案存入tree[]中。

下面代码有一点需要注意，因为之前编写prim模板时将变量n定义为节点数量，而本题题干中定义m才为需要计算的节点的数量，n则为总节点数量。所以此题中m与n的定义与题干中相反。

代码：

#include
#include
using namespace std;
#define maximum 2147483647
#define datasize 15
int key[datasize+1],v[datasize+1],map[datasize+1][datasize+1],heap_size_a,length_a,sum,n;
//以上是prim使用到的变量。 
int parent(int i)
{
    return i/2;
}
int left(int i)
{
    return 2*i;
}
int right(int i)
{
    return 2*i+1;
}
void min_heapify(int a[],int i)
{
    int l=left(i),r=right(i),least;
    if(l<=heap_size_a&&a[l]=1;i--)
        min_heapify(a,i);
}
//以上为堆基本操作，以下为优先队列基本操作  
int heap_extract_min(int a[])
{
    int min=v[1];
    sum+=a[1];
    a[1]=a[heap_size_a];
    v[1]=v[heap_size_a];
    heap_size_a--;
    min_heapify(a,1);
    return min;
}
void heap_decrease_key(int a[],int i,int key)
//key不能大于元素i的值 
{
    a[i]=key;
    while(i>1&&a[parent(i)]>a[i])
    {
        swap(a[i],a[parent(i)]);
        swap(v[i],v[parent(i)]);
        i=parent(i);
    }
}
void prim(int r)
{
    for(int i=1;i<=datasize;i++)
    {
        key[i]=maximum;
        v[i]=i;
    }
    key[r]=0;
    length_a=n;
    build_min_heap(key);
    while(heap_size_a>=1)
    {
        int u=heap_extract_min(key);
        for(int i=1;i<=heap_size_a;i++)
            if(map[u][v[i]]double(sum)/double(total))
        //若当前方案中的比值小于最小比值。 
        {
            ratio=double(sum)/double(total);
            return true;
        }
        return false;
    }
    bool check=false;
    //check用于判断当前以order个点为基础延伸出的方案中是否有比值小于ratio的方案。 
    for(int i=start,res;i<=m-(n-order);i++)
    {
        map[order][0]=i;
        for(int j=1;j<=order;j++)
        //利用original[][]构建order个节点的新邻接矩阵map[][]。 
            map[order][j]=map[j][order]=original[i][map[j][0]];
        if(dfs(i+1,order+1,total+val[i]))
        //若以当前order个节点为基础延伸出的方案中有比值小于ratio的方案。 
        {
            tree[order]=i;
            //用tree[]记录下更优方案中的第order个节点i。 
            check=true;
        }
    }
    return check;
}
int main()
{
    while(scanf("%d%d",&m,&n)&&(m||n))
    {
        intput();
        ratio=100;
        //初始化ratio为一个不可能达到的最大值。（n*100）/(n*1-1)趋近于100。 
        dfs(1,1,0);
        for(int i=1;i<=n;i++)
        //输出结果。 
            if(i-n)
                printf("%d ",tree[i]);
            else
                printf("%d\n",tree[i]);
    }
}

发表回复取消回复