少年Q

用户名：yin19990129

访问量：25361

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

[传智杯]软件工程实习（C++描述）只做最好的思路！
浏览：380

[传智杯]程序员节发橙子（C++描述）只做最好的思路！
浏览：487

[传智杯]众数出现的次数-题解(C++代码)只做最好的思路！
浏览：191

你可能喜欢

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

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

　　作者: 少年Q　　　　发表时间：2020-05-06 17:09:43 浏览：201　|　评论：0　

原题链接：最优比例生成树练习

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

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

【出圈】（C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

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

评论区

精彩推荐

C二级辅导-计负均正（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

Pascal三角（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

DNA （C语言描述，蓝桥杯）

C语言训练-数字母（C语言代码）

1014题解

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

企业奖金发放（C语言代码）

少年Q

TA的其他文章

你可能喜欢

【出圈】 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

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

评论区

精彩推荐

C二级辅导-计负均正 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

Pascal三角 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

DNA （C语言描述，蓝桥杯）

C语言训练-数字母 （C语言代码）

1014题解

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

企业奖金发放 （C语言代码）

【出圈】（C语言代码）

母牛的故事（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

Pascal三角（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言训练-数字母（C语言代码）

企业奖金发放（C语言代码）