C++足球队的问题,如何使用搜索算法实现,图在下面

Problem Description
Falling Stocks. Bankrupted companies. Banks with no Cash. Seems like the best time to invest: ``Think I'll buy me a football team!"

No seriously, I think I have the solution to at least the problem of cash in banks. Banks nowadays are all owing each other great amounts of money and no bank has enough cash to pay other banks' debts even though, on paper at least, they should have enough money to do so. Take for example the inter-bank loans shown in figure (a). The graph shows the amounts owed between four banks (A ...D). For example, A owes B 50M while, at the same time, B owes A 150M. (It is quite common for two banks to owe each other at the same time.) A total amount of 380M in cash is needed to settle all debts between the banks.

In an attempt to decrease the need for cash, and after studying the example carefully, I concluded that there's a lot of cash being transferred unnecessarily. Take a look:

  1. C owes D the same amount as D owes A, so we can say that C owes A an amount of 30M and get D out of the picture.
  2. But since A already owes C 100M, we can say that A owes C an amount of 70M.
  3. Similarly, B owes A 100M only, (since A already owes B 50M.) This reduces the above graph to the one shown in figure (b) which reduces the needed cash amount to 190M (A reduction of 200M, or 53%.)
  4. I can still do better. Rather than B paying A 100M and A paying 70M to C, B can pay 70M (out of A's 100M) directly to C. This reduces the graph to the one shown in figure (c). Banks can settle all their debts with only 120M in cash. A total reduction of 260M or 68%. Amazing!

I have data about inter-bank debts but I can't seem to be able to process it to obtain the minimum amount of cash needed to settle all the debts. Could you please write a program to do that?

Input
Your program will be tested on one or more test cases. Each test case is specified on N + 1 lines where N < 1, 000 is the number of banks and is specified on the first line. The remaining N lines specifies the inter-bank debts using an N×N adjacency matrix (with zero diagonal) specified in row-major order. The ith row specifies the amounts owed by the ith bank. Amounts are separated by one or more spaces. All amounts are less than 1000. The last line of the input file has a single 0.

Output
For each test case, print the result using the following format:

k . B A

where k is the test case number (starting at 1,) is a space character, B is the amount of cash needed before reduction and A is the amount of cash after reduction.

Sample Input
4
0 50 100 0
150 0 20 0
0 0 0 30
30 0 0 0
0

Sample Output
1. 380 120

0

1个回答

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C++足球队的问题,如何使用搜索算法实现,图在下面
Problem DescriptionrnFalling Stocks. Bankrupted companies. Banks with no Cash. Seems like the best time to invest: ``Think I'll buy me a football team!"rnrnNo seriously, I think I have the solution to at least the problem of cash in banks. Banks nowadays are all owing each other great amounts of money and no bank has enough cash to pay other banks' debts even though, on paper at least, they should have enough money to do so. Take for example the inter-bank loans shown in figure (a). The graph shows the amounts owed between four banks (A ...D). For example, A owes B 50M while, at the same time, B owes A 150M. (It is quite common for two banks to owe each other at the same time.) A total amount of 380M in cash is needed to settle all debts between the banks.rnrn![](http://acm.hdu.edu.cn/data/images/con208-1007-1.JPG)rnrnIn an attempt to decrease the need for cash, and after studying the example carefully, I concluded that there's a lot of cash being transferred unnecessarily. Take a look:rnrn1. C owes D the same amount as D owes A, so we can say that C owes A an amount of 30M and get D out of the picture.rn2. But since A already owes C 100M, we can say that A owes C an amount of 70M.rn3. Similarly, B owes A 100M only, (since A already owes B 50M.) This reduces the above graph to the one shown in figure (b) which reduces the needed cash amount to 190M (A reduction of 200M, or 53%.)rn4. I can still do better. Rather than B paying A 100M and A paying 70M to C, B can pay 70M (out of A's 100M) directly to C. This reduces the graph to the one shown in figure (c). Banks can settle all their debts with only 120M in cash. A total reduction of 260M or 68%. Amazing!rnrnI have data about inter-bank debts but I can't seem to be able to process it to obtain the minimum amount of cash needed to settle all the debts. Could you please write a program to do that?rn rnrnInputrnYour program will be tested on one or more test cases. Each test case is specified on N + 1 lines where N < 1, 000 is the number of banks and is specified on the first line. The remaining N lines specifies the inter-bank debts using an N×N adjacency matrix (with zero diagonal) specified in row-major order. The ith row specifies the amounts owed by the ith bank. Amounts are separated by one or more spaces. All amounts are less than 1000. The last line of the input file has a single 0.rn rnrnOutputrnFor each test case, print the result using the following format:rnrnrnk . B Arnrnrnwhere k is the test case number (starting at 1,) is a space character, B is the amount of cash needed before reduction and A is the amount of cash after reduction.rn rnrnSample Inputrn4rn 0 50 100 0rn150 0 20 0rn 0 0 0 30rn 30 0 0 0rn0rn rnrnSample Outputrn1. 380 120
蓝桥杯 历届试题 九宫重排 经典八数码问题 A*算法+康托展开
问题描述   如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。   我们把第一个图的局面记为:12345678.   把第二个图的局面记为:123.46758   显然是按从上到下,从左到右的顺序记录数字,空格记为句点。   本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。 输入格式   输入第一行包含九宫的初态,第二行包含九宫的终态。 输
数据结构编程笔记二十二:第七章 图 拓扑排序算法的实现
上次我们介绍了图的最短路径算法的实现,这次介绍基于邻接表的拓扑排序算法的实现。还是老规矩:程序在码云上可以下载。 地址:https://git.oschina.net/601345138/DataStructureCLanguage.git本次拓扑排序程序共用到以下源文件,有一些已经在之前的文章介绍过。还是和以前一样,所有源文件需要放在同一目录下编译。 my_constants.h 各种状态
Kmeans 聚类算法评估足球比赛
Spark MLlib 机器学习—Kmeans 聚类算法分析足球比赛 一、实验介绍 1.1 内容介绍 K-means 算法采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为类簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means 算法以欧式距离作
图的遍历——深度优先搜索算法
类似广度优先搜索,深度优先搜索算法的定义:首先访问图G任意顶点v,并将其标记为已访问过,然后依次从v出发搜索v的每个邻接点(子节点)w。若w未曾访问过,则以w为新的出发点继续深度优先遍历,直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。 其实理解了广度优先搜素算法,理解这个也是顺带的
图的广度优先遍历BFS(邻接矩阵实现)c语言
广度优先遍历也叫广度优先搜索(Breadth First Search)。它的遍历规则:先访问完当前顶点的所有邻接点。先访问的顶点的邻接点先于后访问顶点的邻接点被访问。算法思想:使用队列的数据结构(FIFO (First In First Out)),将一个顶点加入队列,然后在队列中删除顶点,并且将该顶点相连的所有顶点依次加入队列中,再循环处理这些顶点,直至所有顶点均被访问。(类似树的层序遍历)算...
罗马尼亚度假问题
代价一致的宽度搜索、有限制的深度优先搜索、A*算法、贪婪算法解决罗马尼亚度假问题!
最大流Dinic C语言实现(详细)--poj 3281
//Dinic最大的不同就是分层找增长路径。。。, //我们知道一般是用BFS来找一个增长路径,从中心一层一层地向外扩散 //但是Dinic也是一层一层的向外找,但是它每层只选择一个一个顶点就跳到下一层中接着寻找 #include #define N 1000 #define MAX 0x3f3f3f3f #define min(x,y) ((x>y)?(y):(x))//定义宏 int map[
图 深度优先遍历 广度优先遍历 非递归遍历 图解算法过程
图 深度优先遍历 广度优先遍历 图解算法过程
人工智能A*算法C实现
一、实验内容 对下图所示的状态空间图用A*算法进行搜索: 其中A为起始节点,E为目标节点,各节点的启发值表示在括号内。 二、实验设计(原理分析及流程) A* 是启发式搜索算法。该算法创建两个表:OPEN(类似于回溯算法中的NSL,它列出已经产生但其孩子还未被分析的状态)和CLOSED(记录已经分析了的状态,为回溯算法中的DE与SL列表的联合)。 算法预先将初始节点放入OPEN表,从初始节
回溯算法之装载问题
/* 1.因为很多变量多要在两个main和Backtrack中共用,所以就把这些公用的变量设置为全局变量, 在函数中直接赋值而不能再次定义 否则赋值给的就是局部变量在其他的函数中不能使用 2.c++中数组的定义: 1.数组的长度只能在[]中定义,而且必须是常量表达式或用const修饰的变量且该变量在函数运行之前  就已经知道值是多少; 2.int a[4]={1,2,3,4};{}称为
算法设计分析中 图的m色的着色问题 的源程序
对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。
深度搜索算法C语言实现--以走迷宫为例
深度搜索算法C语言实现,以走迷宫为例子
多段图动态规划算法的实现
#include #include #include #include #include #define MAX_VERTEX_NUM 20 #define MAX_VALUE_TYPE INT_MAX typedef int VertexType; typedef struct node{ VertexType adjvex; int weight; //权值
BM搜索算法C实现
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm #include &amp;lt;stdint.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; #define ALPHABET_LEN 256 #define NOT_FOUND patlen #define max(a, b) ((a...
回溯经典算法之四皇后问题
1.问题概述:在一个4*4的方格中住着四个皇后,他们之间都不友好,相邻就会打架,现在要进行查找能够满足:每行每列每个斜线都只有一个皇后,才能没有打架发生2.思路:这里需要这样进行查找,第一个皇后先在第一行第一列开始假定位置,然后第二行第二个皇后满足条件来摆放,如果到后面有皇后不能放在能满足条件地方了时就回到她的前一个皇后并换一个地方,或者在前一个。。。就这样,最后得到了结果是2413定义一个数组a[
关键路径的算法设计与实现(C语言)
关键路径的算法设计与实现,c语言,可运行.....
图的遍历之深度优先搜索算法&&广度优先优先算法的实现
一.序 和树的遍历类似,我们希望从图中的某一个顶点出发访问图中其余顶点,保证每个顶点只被访问一次,这一过程叫做图的遍历。图的遍历算法是求解图的连通性问题(最小生成树),拓扑排序,求关键路径的基础。 而为了保证同一个顶点不被访问多次,在遍历图的的过程中,必须记下访问过的顶点。为此,需要设立一个辅助数组visited[0..n-1],初始值设置为0或假,这样其不为0或者为真时,表示此顶点已经被访问过
实验一 搜索算法问题求解
一、实验目的1.了解4种无信息搜索策略和2种有信息搜索策略的算法思想; 2.能够运用计算机语言实现搜索算法; 3.应用搜索算法解决实际问题(如罗马尼亚问题); 4.学会对算法性能的分析和比较二、实验的硬件、软件平台硬件:计算机 软件:操作系统:WINDOWS 2000 应用软件:C,Java或者MATLAB三、实验内容及步骤使用搜索算法实现罗马尼亚问题的求解 1:创建搜索树;
python搜索算法实现——(二)贪婪算法
贪婪算法简介 假设你办了个广播节目,要让全美国50个州的听众都能听得到,为此, 你需要决定在哪些广播台播出。每个广播台台播出都需要费用,所以你需要尽可能地在更少的广播台播出节目。现有广播台名单如下: 每个广播台都覆盖不同的范围,但是有些是重复的 如何才能找出覆盖全美50个州的最小广播台集和呢?先提供一种方法: (1)列出每种可能的广播台集和,称之为幂集,总共有2^n种集和 (2)...
C语言实现图的邻接表的创建以及深度搜索和广度搜索
#include #include #define MAX_VALUE 10 typedef struct EdgeNode{//边顶点 int index;//该顶点下标 struct EdgeNode *next;//存储下一个边顶点 }EdgeNode; typedef struct HeadNode{//表顶点 char data; EdgeNod
装载问题——搜索回溯算法
装载问题c++
算法设计与分析:第五章 回溯法 5.3图的着色问题
/* 图的着色问题: 给定无向图G(V,E),用m种颜色为图中每个 顶点着色,要求每个顶点着一种颜色,并 且使得相邻两个顶点之间的颜色不同 分析: 用一个n元组描述图的一种颜色(x1,x2,...,xn),xi属于[1,m],1<=i<=n 为了用m种颜色对n个顶点着色,就有m^n中可能颜色组合,状态空间树是高度为n 的完全m叉树 约束方程: x[i] != x[j],若顶点i与顶点j相邻
单源点最短路径的贪心算法
使用贪心算法实现单源点最短路径问题,C语言实现
图的m着色问题(回溯法-满m叉树)
1.问题描述: 给定无向连通图G和m种不同的颜色。用这些颜色为图G的所有顶点着色,每个顶点着一种颜色。每条边的2个顶点颜色不同。称为图的m着色。 求有多少种方法为图可m着色。 示例: 该无向连通图每个顶点有3种着色方式,试求图的m着色方案有几种 有6种 具体过程在下面 2.算法设计: 很明显,约束条件为相邻顶点的颜色不同。 条件:相邻 & 颜色不同 图的临接矩阵为a
已知有十六支男子足球队参加2008 北京奥运会。写一个程序,把这16 支球队随机分为4 个组。 注:参赛球队列表见附录 注2:使用Math.random 来产生随机数。(也可以使用其它方法) 2. 2
package whp.practice12; import java.util.ArrayList; import java.util.List; import java.util.Random; /** * Created by whp on 2018/7/30. */ public class Test { public static void main(Stri...
C语言实现有向无环图的拓扑排序算法
对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者在AOV网中不存在入度为0的顶点为止。 这里图使用的数据结构是邻接表,并且在顶点表加入顶点入度一项。 以下程序在DEV C++中编译运行通过。 #include #include #define MAXVEX 20 typedef st
历届试题 九宫重排 (bfs 八数码问题)
问题描述   如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。   我们把第一个图的局面记为:12345678.   把第二个图的局面记为:123.46758   显然是按从上到下,从左到右的顺序记录数字,空格记为句点。   本题目的任务是已知九宫的初态和终态,求最少经过
4.梵塔问题:
4.梵塔问题:有3个柱子(1,2,3)和3个不同尺寸的圆盘(A,B,C)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上。最初,全部3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。 编程实现梵塔问题算法,演示算法过程(即圆盘在柱子之间移动过程)和结果。
C语言资源分配问题代码
C语言资源分配问题代码,算法设计与分析课程中的
一字棋游戏设计-极大极小搜索
1.     问题定义 一字棋游戏,包括两个选手。用户可以在一个3*3的棋盘上任意的选择空闲的位置拜访棋子,最早在水平方向上,或者垂直方向上或者对角线方向上形成三子一线者获胜。棋盘如图1所示。这里我们实现的是用户和计算机进行对弈。本程序要实现的是让计算机可以自动的根据当前棋局计算下一步对自己最有利的走步,尽可能的朝着可以让计算机获胜的方向走步。需要采用极大极小搜索算法。 图1.一字棋棋盘
A*算法求解迷宫
[cpp] view plaincopy #include   #include   #include   using namespace std;    //方向向量  int direc[4][2]={{0,1},{-1,0},{0,-1},{1,0}};    //封闭,开放列表标记  enum Flag  {      SEAL,      OPEN,      UNVISITE
深度优先、广度优先和A*算法实现的重排九宫问题
问题描述 在3×3的方格上分别放置1,2,3,4,5,6,7,8,9的八张排,初始状态为S0,目标状态为Sg,计算出从S0到Sg的方法。 代码及说明 /**//****************************************************************************** * 使用深度优先、广度
020-寻找图的关节点-dfs-《算法设计技巧与分析》M.H.A学习笔记
在多于两个顶点的无向图G中,存在一个顶点v,如果有不同于v的两个顶点u和w,在u和w间的任何路径都必定经过顶点v,则称v为关节点。 一种更形象的说法: 关节点也叫割点,连通图中删去割点会被分割成几个连通分量。
多段图的最短路径问题-----动态规划法
对多段图,求最短路径,如图: 对其使用动态规划法: 阶段:将图中的顶点划分5个阶段,k 状态:每个阶段有几种供选择的点s 决策:当前状态应在前一个状态的基础上获得。决策需要满足规划方程 规划方程:f(k)表示状态k到终点状态的最短距离。 初始条件:f(k)=0; 方程:f(k-1)=min{f(k)+W(k-1,k)}其中W(k-1,k)表示状态k-1到状态k的距离 代码如下:
回溯之符号三角形问题
符号三角形问题 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2个异号下面都是“-”。 在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 •解向量:用n元组x[1:n]表示符号三角形的第一行。 •可行性约束函数:当前符号
修道士与野人问题——C++源代码,伪代码,详细分析
前言:这一个经典的问题,可以把问题转换成数据结构中的 图 来解决。
动态规划的算法解决多段图问题
给定一个有向多段图,使用动态规划的算法思想设计出算法实现多段图的最短路径问题,并输出路径!
聚类分析-实现亚洲足球聚类
Description:利用K-Means算法实现亚洲足球的聚类; 下图是亚洲15只球队在2005年-2010年间大型杯赛的战绩: 下图是0-1规格化后的数据: Analysis: 1.确定K值及K个初始类簇中心点的选取(详见Blog底部链接) 设 K = 3,即将这15支球队分成3个集团; 现抽取日本、巴林、泰国的值作为3个簇的种子,即初始化3个簇的中心为
广度优先搜索的c语言实现
今天下午有时间,好奇图论,所以把算法导论的22章的图论的基础给看了一下,最后那个强连通分量我没看,不知道有什么用处,等到要用的时候再看吧,一切按照兴趣走。晚上花了两个多小时把广度优先搜索的部分给实现了一遍,感觉还是比较棒的。整个过程中的数据结构方面,我没有因为实现方面的原因而浪费空间,尽力实现了这个广度优先搜索。     直接上附上代码,以后直接在代码上注释吧,不过多地写废话了,一些概念都在书上
文章热词 双目视觉问题 特征点问题 相机标定问题 最优化问题 Matplotlib柱形图和盒图
相关热词 c++ dijkstra算法实现 c++ elman算法实现 c++ strcpy使用存在问题 区块链问题 python爬图教程