按E搞比利

用户名：1096581839

访问量：8653

签　名：

重度抑郁,休学在家,无聊学编程

等　　级
排　　名	1997
经　　验	2513
参赛次数	0
文章发表	22
年　　龄	20
在职情况	学生
学　　校	中国计量大学
专　　业	数学

　　自我简介：

一个重度抑郁症患者,已经吃药两年.......

TA的其他文章

[搞比利]题解2029：22.获取树的规模（C++代码）
浏览：322

[搞比利]题解2030：23.树的中序遍历（C++代码）
浏览：402

[搞比利]题解2033：26.网络互通（C++代码）
浏览：620

你可能喜欢

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

[搞比利]2051题-56.最优比例生成树练习-题解(C++代码)

　　作者: 按E搞比利　　　　发表时间：2019-12-08 18:20:37 浏览：345　|　评论：0　

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

//prim加迭代
	//这玩意叫01分数规划,视频没说
	//prim返回的浮点数得跟0.00001比,跟0比会有一个超时
	//wok卡我两天 我们那垃圾大学这么重要的东西都不给讲
	#include<bits/stdc++.h>
	using namespace std;
	int minint=-10000000;
	int a[50][50];
	int b[50][1000];
	double f[50][50];
	int x[50],n;
	double dist[50];
	int tot;
	struct node{
	int x,y;
	}edge[50];
	bool used[50];
	double ans;
	double prim(){
	int maxv;
	double sum=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){
					edge[++tot].x=x[mark];
					edge[tot].y=mark;}
				used[mark]=1;
				sum+=dist[mark];
				for(j=1;j<=n;j++)
					if(f[mark][j]>dist[j])x[j]=mark,dist[j]=f[mark][j];}
				return sum;}
	int main(){
	int sumb,suma,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){
		sumb=suma=0;
		for(i=1;i<=n;i++){
			sumb+=b[edge[i].x][edge[i].y];
			suma+=a[edge[i].x][edge[i].y];}
		ans=(suma+0.0)/sumb;
		tot=0;}
	cout<<fixed<<setprecision(3)<<ans;}

0.0分

1 人评分

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

按E搞比利

TA的其他文章

你可能喜欢

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

兰顿蚂蚁（C语言代码）

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

点我有惊喜！你懂得！

C语言训练-求PI* （C语言代码）

[搞比利]2051题-56.最优比例生成树练习-题解(C++代码)

评论区

精彩推荐

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

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

简单的a+b （C语言代码）

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

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

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

矩阵乘方（C语言代码）

1054题解

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

GC的苦恼（C语言代码）

按E搞比利

TA的其他文章

你可能喜欢

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

兰顿蚂蚁 （C语言代码）

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

点我有惊喜！你懂得！

C语言训练-求PI* （C语言代码）

[搞比利]2051题-56.最优比例生成树练习-题解(C++代码)

评论区

精彩推荐

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

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

简单的a+b （C语言代码）

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

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

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

矩阵乘方 （C语言代码）

1054题解

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

GC的苦恼 （C语言代码）

兰顿蚂蚁（C语言代码）

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

　　评论区

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

矩阵乘方（C语言代码）

GC的苦恼（C语言代码）