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

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

《人工智能》第三章：搜索算法问题求解

020-寻找图的关节点-dfs-《算法设计技巧与分析》M.H.A学习笔记

/* 1.因为很多变量多要在两个main和Backtrack中共用，所以就把这些公用的变量设置为全局变量， 在函数中直接赋值而不能再次定义 否则赋值给的就是局部变量在其他的函数中不能使用 2.c++中数组的定义： 1.数组的长度只能在[]中定义，而且必须是常量表达式或用const修饰的变量且该变量在函数运行之前  就已经知道值是多少； 2.int a[4]={1,2,3,4};{}称为

都做过倒水的问题，有一个3升和5升的水桶和无限的水，现在要求桶中恰好装入4升水。POJ3414就是这类的倒水问题，给你两个桶，容量为A,B。现在要求称出C升水。（1&amp;lt;=A,B&amp;lt;=100，C&amp;lt;=MAX(A,B)）     并且要使操作次数最少，打印最少次数和操作。     操作次数最少，显然是广度优先搜索可以快速达到要求。对于两个桶的状态，它一共有六种操作：把A倒满，把...

C语言实现图的邻接表的创建以及深度搜索和广度搜索
#include #include #define MAX_VALUE 10 typedef struct EdgeNode{//边顶点 int index;//该顶点下标 struct EdgeNode *next;//存储下一个边顶点 }EdgeNode; typedef struct HeadNode{//表顶点 char data; EdgeNod

1993B 数学建模足球排名比赛问题
1993年数学建模B题 足球排名比赛问题
A*算法实现走迷宫（可应用于游戏人物自动寻路）

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...

1. 深度优先遍历(Depth-First Traversal)2.1 图的深度优先遍历的递归定义　　假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶

11、16支足球队随机分组