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
用k-means对亚洲足球队做聚类
背景知识 亚足联AFC: 1954年成立,总部马来西亚吉隆坡。 负责管理亚洲区足球事务,举办各项国家级及俱乐部级赛事,协助国际足联举行世界杯预选赛及4年一度的亚洲杯。 47个成员协会,包括阿富汗、缅甸、中国台北、中国香港、印度尼西亚、日本、韩国、巴基斯坦、菲律宾、新加坡、越南等。 分为两大势力——东亚及西亚,东亚包括有日本、韩国、中国、澳大利亚(来自大洋洲的澳大利亚于2006年加入亚足联),西亚有...
回溯算法求解迷宫问题
迷宫的存储结构以二维数组来存储,用0,1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法,其实迷宫问题是一种特殊形式图的问题,因此,迷宫总量可转化为图的问题来解决。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.本文采用回溯法求解迷宫路径,算法用到数据结构中的栈。
足球队排名问题
本论文针对足球的排名问题设计一个依据各队的成绩排出各队的名次的模型。它首先对用来排名次的数据是否充分作出判断,在能够排名次时对数据的可依赖程度作出估计,然后给出名次。 文中证明了这个名次正是比赛成绩所体现的各队实力的顺序。 文中将看到此模型充分考虑了排名结果对各场比赛成绩的重要性的反馈影响,基本上消除了由于比赛对手的强弱不同造成的不公平现象。文中还证明了模型的稳定性,这保证了各队在发挥水平上的小的波动不会对排名顺序造成大的变动。以下是我对8强进行分析的过程,得出公正合理的判断。
数学建模优秀论文_一个给足球队排名次的方法.rar
数学建模优秀论文_一个给足球队排名次的方法.rar 数学建模优秀论文_一个给足球队排名次的方法.rar
回溯算法----图的M着色问题
问题: 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色,求有多少种方法。 邻接矩阵: 如下无向图结构和其邻接矩阵表示,共5个顶点      如何判断第k个顶点的着色是否与其相邻顶点的着色冲突: 判断第1---(k-1)个顶点,若"graph[k][i]==1 && color[i]!=colo
深度优先搜索算法和广度优先搜索算法解八数码问题
用C#做的程序,用两种不同的算法解八数码问题,现与大家分享
从广度优先搜索,深度优先搜索,A*算法多方面算法来解决八数码问题
从广度优先搜索,深度优先搜索,A*算法多方面算法来解决八数码问题 人工智能的作业 八数码问题 用MFC做的,有界面 很好, 给大家共享下
《人工智能》第三章:搜索算法问题求解
问题求解算法的性能 完备性:当问题有解时,这个算法是否能保证找到解? 最优性:搜索策略是否能找到开销最小的最优解? 时间复杂度:找到解需要花费多长时间? 空间复杂度:在执行搜索的过程中需要多少内存? 概念: 典型度量方式:状态空间图大小,|V|+|E|,其中V是图中顶点(结点)的集合,E是图中边(连接)的集合。 复杂度通常由三个量确定 b,分支因子,或者说任何结点的最多后继 d,目标结点所在...
一个给足球队排名次的方法_B题
足球排名一个:给足球队排名次的方法_B题,方便大家参考~~希望可以帮助到大家~~
足球对排名问题 数学建模
在足球比赛中,我们可以得到各个球队每场比赛的成绩,那么,应如何根据这些给定的比赛成绩给参赛的球队进行排名?
深度优先搜索实现八数码问题
人工智能的作业,用深度优先遍历实现八数码问题,可以设置搜索深度。
020-寻找图的关节点-dfs-《算法设计技巧与分析》M.H.A学习笔记
在多于两个顶点的无向图G中,存在一个顶点v,如果有不同于v的两个顶点u和w,在u和w间的任何路径都必定经过顶点v,则称v为关节点。 一种更形象的说法: 关节点也叫割点,连通图中删去割点会被分割成几个连通分量。
回溯算法之装载问题
/* 1.因为很多变量多要在两个main和Backtrack中共用,所以就把这些公用的变量设置为全局变量, 在函数中直接赋值而不能再次定义 否则赋值给的就是局部变量在其他的函数中不能使用 2.c++中数组的定义: 1.数组的长度只能在[]中定义,而且必须是常量表达式或用const修饰的变量且该变量在函数运行之前  就已经知道值是多少; 2.int a[4]={1,2,3,4};{}称为
三、【图算法】DFS应用-拓扑排序
深度优先搜索(DFS)算法是最重要的图遍历算法,基于DFS框架,可以导出大量的图算法,图的拓扑排序即为其中一个很典型的例子。 拓扑排序:给定一个有向图,如何在保证“每个顶点都不会通过边,指向其在此序列中的前驱顶点”这一前提下,将所有顶点排成一个线性序列。 例如: 在编写教材时,由于各个知识点之间具有一定的依赖关系,如何将这些知识点串联为一份教学计划,保证在整个授课进程中,每节课的基本知识点均...
浅谈拓扑排序(基于dfs算法)
假设有n个任务,有m个有序对(u,v),表示任务u应该排在任务v之前,那么怎样将这些任务按照顺序排列起来呢?比如有三个有序对(1,4),(3,2),(1,3)排列起来就是1,3,2,4 。尽管还有其他可能(如1,4,3,2),但我们只需找出一种即可,注意:有些情况无法排序,如(1,2),(2,3),(3,1)。我们把每个任务看成一个点,将每个有序对看成有向边,则形成了一个有向图,由题意可知这个有向...
算法设计分析中 图的m色的着色问题 的源程序
对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。 对于图的m色着色问题。
迷宫寻路问题——A*算法
迷宫寻路问题是人工智能中的有趣问题,如何表示状态空间和搜索路径是寻路问题的重点,本文的主要内容是A*搜索算法的理解和应用,首先对基本知识和算法思想进行了解,再通过其对迷宫问题求解应用,编写 Python 程序进行深入学习。
搜索算法之深度优先搜索和广度优先搜索
所谓深度优先搜索:就是一条道走到黑,不碰南墙不回头的那种。        广度优先搜索:就是从你所站的位置向周围扩散性的搜索,通俗来讲,就是你在黑夜里眼睛掉了,你肯定是趴在地上,手向四周摸索,摸不到会到下一步摸索。 一道简单的例题的两种不同的做法: 问题描述:(自己编的,绝对原创),小明和女神小红一起出去游玩,偶然发现一座上古迷宫(里面可能有科学不能解释的神奇物品),好奇心特别重的小红想着里...
子图同构问题Ullmann 算法(二)
写在前面的画以上的内容均出自这篇论文ullmann algorithm,所有的表述竟可能的和论文中的表述保持一致。 我要做的事情就是竟可能的讲的很清楚,尽可能的做到准确完备。谨以此系列献给 my best love, grandpa~ 还有昆明宝石蓝的天空,2月的梨花,三月的樱花,10月的桂花,星光璀璨的星空陪我入梦乡,安静而又安抚人的环境,总是让我心很静,那些美好的事物总是想让我保持一颗干净温暖
贪心算法区间图着色问题
问题来自算法导论十六章,使用尽可能少的教室对一系列活动进行调度。 思路,把能兼容的活动放在以一个教室。 先把所有活动按结束时间递增的顺序排列,方便以后的循环。选取快速排序,期望时间复杂度为nlgn,最坏为n^2.快排我都有点忘记了,但是看了一下算法导论的图就秒懂了,可见学算法结合图形还是很重要的事情。 循环活动,把每个活动往教室里填,看活动是否与教室里已有的活动兼容(也就是开始时间是否比最后...
广度优先搜索BFS(简单)
    都做过倒水的问题,有一个3升和5升的水桶和无限的水,现在要求桶中恰好装入4升水。POJ3414就是这类的倒水问题,给你两个桶,容量为A,B。现在要求称出C升水。(1&amp;lt;=A,B&amp;lt;=100,C&amp;lt;=MAX(A,B))     并且要使操作次数最少,打印最少次数和操作。     操作次数最少,显然是广度优先搜索可以快速达到要求。对于两个桶的状态,它一共有六种操作:把A倒满,把...
采用贪心法求解着色问题(JAVA)
贪心法求解着色问题。 给图的所有结点着色,限制是一条边的两个端点不能用同样的颜色,要求所使用的不同颜色的数目最少。 “贪心”算法的思想是首先 用第一种颜色对图中尽可能多的顶点着色(“尽可能多”表现出“贪心”);然后用第二种颜色对余下的顶点中尽可能多的顶点着色;如此等等,直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时,我们采取下列步骤: (1)选取某个未着色的顶点,并...
随机选择算法
随机选择算法 问题 从一个无序数组中求出第k大的数。 解法 原理与快速排序相似,在快排基础上用数组中随机元素代替第一个元素,这样可以保证不存在一组特定的数据能使该算法出现最坏情况(例如对于快速排序来说,最坏情况是序列中元素已经接近有序,这时时间复杂度会劣化到O(n2)O(n2)O(n^2))。 利用randPartition函数重排数组,使得随机元素p左边的数均小于等于p,右边的数均大于...
C语言实现图的邻接表的创建以及深度搜索和广度搜索
#include #include #define MAX_VALUE 10 typedef struct EdgeNode{//边顶点 int index;//该顶点下标 struct EdgeNode *next;//存储下一个边顶点 }EdgeNode; typedef struct HeadNode{//表顶点 char data; EdgeNod
单源点最短路径的贪心算法
使用贪心算法实现单源点最短路径问题,C语言实现
1993B 数学建模足球排名比赛问题
1993年数学建模B题 足球排名比赛问题
A*算法实现走迷宫(可应用于游戏人物自动寻路)
环境:win10   语言: Python3.6   编译器:pycharm 先看效果图(红色:终点  黄色:起点   黑色:障碍  绿色路径) 一、A*算法: A*算法是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序,使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点...
五、字符串类的实现及子串查找算法
一、字符串类的创建问题提出:C语言不支持真正意义上的字符串C语言使用字符数组(“\0”结束)和一组函数实现字符串操作C语言不支持自定义类型,因此无法获得字符串类型。C++中的原生类型系统中是否包含字符串类型?——No!C++通过库来支持字符串类型——标准库。STL和Qt都有自己实现的字符串类型,会出现不兼容的情况。所以我们可以自己实现字符串类来作为一个通用的库来使用。通过面向对象的技术来对C语言中...
python函数,一个足球队在寻找年龄在x岁到y岁的小女孩(包括x岁和y岁)加入。
#4、一个足球队在寻找年龄在x岁到y岁的小女孩(包括x岁和y岁)加入。 #编写一个程序,询问用户的性别(m表示男性,f表示女性)和年龄, 然后显示一条消息指出这个人是否可以加入球队,询问k次后,输出满足条件的总人数。 def search(sex,age,k,x,y): enrollment = 0 for num in range(0,k): sex = input(“请输入孩子性别:”) ag...
算法笔记(III) 状态空间搜索
动态规划 在一般的算法书中,动态规划总是一个复杂的算法设计技巧。在几种普遍涉及的算法设计技巧:穷举、贪心、回溯、分治、动态规划中,动态规划往往是最复杂技巧性最强的一个技巧,但是常常最有效的算法,甚至在一些看似简单的算法中,都蕴含着动态规划的深刻思想,例如最短路径的floyd算法。 理解动态规划往往需要过程,既要阅读书本理解最优子问题结构、马尔可夫性这两个理论要点,同时也要编写程序,理解
深度搜索算法C语言实现--以走迷宫为例
深度搜索算法C语言实现,以走迷宫为例子
回溯法-bfs--迷宫问题的最短路径
迷宫问题怎样才可以得到最短路径: 这里有测试案例: 0-通路,-1为墙,输入为: 测试经过计算机跑过--为: 这样其最短路径为: 核心算法为: findpath(int ** map,const int &start_x,const int &start_y) {     int m=start_x,n=start_y;     Queue Q;
动态规划的算法解决多段图问题
给定一个有向多段图,使用动态规划的算法思想设计出算法实现多段图的最短路径问题,并输出路径!
图的路径搜索
1. 深度优先遍历(Depth-First Traversal)2.1 图的深度优先遍历的递归定义  假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶
实验一 搜索算法问题求解
一、实验目的1.了解4种无信息搜索策略和2种有信息搜索策略的算法思想; 2.能够运用计算机语言实现搜索算法; 3.应用搜索算法解决实际问题(如罗马尼亚问题); 4.学会对算法性能的分析和比较二、实验的硬件、软件平台硬件:计算机 软件:操作系统:WINDOWS 2000 应用软件:C,Java或者MATLAB三、实验内容及步骤使用搜索算法实现罗马尼亚问题的求解 1:创建搜索树;
11、16支足球队随机分组
编程题目: 11.将16支足球队随机分成四组: 科特迪瓦 阿根廷 澳大利亚 塞尔维亚 荷兰 尼日利亚 日本 美国 中国 新西兰 巴西 比利时 韩国 喀麦隆 洪都拉斯 意大利 示例代码: package program.collection.exerc...
贪心法求解图的着色问题
贪心法求解图的着色问题C++源代码,可直接编译运行。 greedy.
贪心算法实现会场安排问题
算法概述:   贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。   贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 问题概述: 学校的小礼堂每天都会有许多活动,
动态规划解多段图问题
使用动态规划求解多段图问题的算法,C语言实现