56.最优比例生成树练习-题解（C++代码）只做最好的思路！

这题还是挺有难度的，老师傅在讲解时给出了最优比例生成树的模板代码，然后我又结合了大神网友的代码后，自己将这题码了一遍。。。其实就是0-1分数规划问题。。
0-1分数规划一般考虑两种做法：prim+迭代或者二分法，这里我承接老师傅的意愿，用的是prim+迭代的方法，代码如下：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
const int minint=-1e7;
int cnt,n;
double ans;
int c[55];
bool used[55];
int a[55][55];
int b[55][55];
double dist[55];
double f[55][55];
struct node{
    int x;
    int y;
}edge[55];
double prim(){
    int maxv;
    double sum=0.0;
    int i,j,mark;
    for(i=1;i<=n;i++){
        dist[i]=minint;
        used[i]=0;
        for(j=1;j<=n;j++){
            f[i][j]=a[i][j]-ans*b[i][j];
        }
    }
    dist[1]=0;
    for(i=1;i<=n;i++){
        maxv=minint;
        mark=0;
        for(j=1;j<=n;j++){
            if(maxv<dist[j]&&!used[j]){
                maxv=dist[j];
                mark=j;
            }
        }
        if(i>1){
            cnt++;
            edge[cnt].x=c[mark];
            edge[cnt].y=mark;
        }
        used[mark]=1;
        sum+=dist[mark];
        for(j=1;j<=n;j++){
            if(dist[j]<f[mark][j]){
                dist[j]=f[mark][j];
                c[j]=mark;
            }
        }
    }
    return sum;
}
int main(){
    int suma,sumb,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&b[i][j]);
        }
    }    
    while(prim()>0.0000001){
        suma=sumb=0;
        for(i=1;i<=n;i++){
            suma+=a[edge[i].x][edge[i].y];
            sumb+=b[edge[i].x][edge[i].y];
        }
        ans=suma*(1.0)/sumb;
        cnt=0;
    }
    printf("%.3lf",ans);
    return 0;
}

需要注意的是：
1.prim返回的浮点数得跟0.0000001比,跟0比会有一个超时。
2.对ans的变化赋值只能在分子上乘1.0，不能在分母上乘1.0，这是个细节，举个例子：
1x(1.0)/2=0.5而(1/2)x(1.0)=0。。。