一个超级难的问题，倾家荡产提问！(229分)

可是如果 N = 199 时，这样的穷举也太多了吧？

199行的。
计算需3秒钟

unit Unit2;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls, Buttons;

type

myPoint = record
path: array[-99..99] of integer;
sum: integer;
nowInt: integer;
end;
TForm2 = class(TForm)
Panel1: TPanel;
ScrollBox1: TScrollBox;
Image1: TImage;
BitBtn1: TBitBtn;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button4: TButton;
Button5: TButton;
procedure PaintBox1Paint(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure BitBtn1Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form2: TForm2;
data: array[-99..99, -99..99] of myPoint;

implementation

{$R *.dfm}

procedure TForm2.PaintBox1Paint(Sender: TObject);
var
i, j, c: integer;
x, y, oldx, oldy: integer;
idx: integer;
str: string;
bmp: TBitmap;
begin

end;

procedure TForm2.FormCreate(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
data[j * 2 - c - 1].nowInt := 1 + Random(100);
end;

y := 10;

Image1.Picture.Bitmap := TBitmap.Create;
Image1.Picture.Bitmap.PixelFormat := pf4bit;
Image1.Picture.Bitmap.Width := 2900;
Image1.Picture.Bitmap.Height := 2900;
with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;

end;

procedure TForm2.BitBtn1Click(Sender: TObject);
var
oldx, oldy, x, y, i, j, c, nowidx, from: integer;
begin

data[-99][0].sum := data[-99][0].nowInt;
data[-99][0].path[-99] := 0;
for i := -98 to 0 do
begin
c := 100 - abs(i);

nowidx := 1 * 2 - c - 1;
data[nowidx].sum := data[nowidx].nowInt + data[i - 1][nowidx + 1].sum;
data[nowidx].path := data[i - 1][nowidx + 1].path;
data[nowidx].path := nowidx;

nowidx := c * 2 - c - 1;
data[nowidx].sum := data[nowidx].nowInt + data[i - 1][nowidx - 1].sum;
data[nowidx].path := data[i - 1][nowidx - 1].path;
data[nowidx].path := nowidx;

for j := 2 to c - 1 do
begin
nowidx := j * 2 - c - 1;

from := nowidx - 1;
if data[i - 1][nowidx + 1].sum > data[i - 1][from].sum then
from := nowidx + 1;

data[nowidx].sum := data[nowidx].nowInt + data[i - 1][from].sum;
data[nowidx].path := data[i - 1][from].path;
data[nowidx].path := nowidx;
end;
end;

for i := 1 to 99 do
begin
c := 100 - abs(i);

nowidx := 1 * 2 - c - 1;
for j := 1 to c do
begin
nowidx := j * 2 - c - 1;

from := nowidx - 1;
if data[i - 1][nowidx + 1].sum > data[i - 1][from].sum then
from := nowidx + 1;

data[nowidx].sum := data[nowidx].nowInt + data[i - 1][from].sum;
data[nowidx].path := data[i - 1][from].path;
data[nowidx].path := nowidx;
end;
end;

// showmessage(inttostr(data[99][0].sum));
with Image1.Picture.Bitmap.Canvas do
begin
y := 10;
Brush.Color := clbtnface;
FillRect(Rect(0, 0, Image1.Picture.Bitmap.Width, Image1.Picture.Bitmap.Height));
Font.Size := 8;
Pen.Color := clred;
pen.Width := 2;
TextOut(1, 1, '总和=' + inttostr(data[99][0].sum));

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[99][0].path = j then
begin
if i <> -99 then
begin
moveto(oldx + 6, oldy + 6);
LineTo(x + 6, y + 6);
end;
oldx := x;
oldy := y;
end;
inc(x, 14)
end;
inc(y, 14);
end;
y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

if data[99][0].path = j then
Font.Color := clred

else
Font.Color := clblack;

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))

end;
inc(x, 14)
end;
inc(y, 14);
end;
end;

end;

procedure TForm2.Button1Click(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
data[j * 2 - c - 1].nowInt := 1 + Random(100);
end;

y := 10;

with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;
BitBtn1.Click;

end;

procedure TForm2.Button2Click(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
data[j * 2 - c - 1].nowInt := j;
end;

y := 10;

with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;
BitBtn1.Click;
end;

procedure TForm2.Button3Click(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
data[j * 2 - c - 1].nowInt := 1;
end;

y := 10;

with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;
BitBtn1.Click;

end;

procedure TForm2.Button4Click(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
data[j * 2 - c - 1].nowInt := 1;
end;

data[-95][0].nowInt := 99;
y := 10;

with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;
BitBtn1.Click;

end;

procedure TForm2.Button5Click(Sender: TObject);
var
x, y, i, j, c: integer;
begin

for i := -99 to 99 do
begin
c := 100 - abs(i);
for j := 1 to c do
if (i mod 2) = 0 then
data[j * 2 - c - 1].nowInt := j
else
data[j * 2 - c - 1].nowInt := c - j + 1;
end;

y := 10;

with Image1.Picture.Bitmap.Canvas do
begin

y := 10;
Pen.Color := clblack;
pen.Width := 1;

for i := -99 to 99 do
begin
x := 10;
for j := -99 to 99 do
begin
if data[j].nowInt <> 0 then
begin

Pen.Color := Font.Color;
Brush.Color := clblue;

Ellipse(x - 2, y - 2, x + 15, y + 15);

TextOut(x, y, inttostr(data[j].nowInt))
end;
inc(x, 14)
end;
inc(y, 14);
end;
end;
BitBtn1.Click;

end;

end.

object Form2: TForm2
Left = 160
Top = 81
BorderStyle = bsSingle
Caption = 'Form2'
ClientHeight = 573
ClientWidth = 792
Color = clBtnFace
Font.Charset = GB2312_CHARSET
Font.Color = clWindowText
Font.Height = -12
Font.Name = '宋体'
Font.Style = []
OldCreateOrder = False
Position = poScreenCenter
OnCreate = FormCreate
PixelsPerInch = 96
TextHeight = 12
object Panel1: TPanel
Left = 0
Top = 0
Width = 792
Height = 41
Align = alTop
Caption = 'Panel1'
TabOrder = 0
object BitBtn1: TBitBtn
Left = 16
Top = 8
Width = 75
Height = 25
Caption = '计算'
TabOrder = 0
OnClick = BitBtn1Click
end
object Button1: TButton
Left = 112
Top = 8
Width = 75
Height = 25
Caption = '随机数据'
TabOrder = 1
OnClick = Button1Click
end
object Button2: TButton
Left = 192
Top = 8
Width = 75
Height = 25
Caption = '特殊数据1'
TabOrder = 2
OnClick = Button2Click
end
object Button3: TButton
Left = 272
Top = 8
Width = 75
Height = 25
Caption = '特殊数据2'
TabOrder = 3
OnClick = Button3Click
end
object Button4: TButton
Left = 352
Top = 8
Width = 75
Height = 25
Caption = '特殊数据3'
TabOrder = 4
OnClick = Button4Click
end
object Button5: TButton
Left = 440
Top = 8
Width = 75
Height = 25
Caption = '特殊数据4'
TabOrder = 5
OnClick = Button5Click
end
end
object ScrollBox1: TScrollBox
Left = 0
Top = 41
Width = 792
Height = 532
HorzScrollBar.Position = 1023
Align = alClient
TabOrder = 1
object Image1: TImage
Left = -1022
Top = 2
Width = 2900
Height = 2900
end
end
end

http://www.efile.com.cn/efile/dfw@97546/sss.rar
199行的

简单的线性规划问题，去找数值计算的书看看就可以了。

图论中的加权路径查找，怎么算忘了，可以查查资料。

向牛人學習...

http://www.efile.com.cn/efile/dfw@97546/sss.rar
199行的
帮忙测试啊！

最短路径求解问题 数据结构

有一个想法 是不是可以用递归的方法
比如求整个路径的值最大，可以现考虑从第一个数下面的那两个数出发求出最大的路径值
以此类推 当然了实现没那么容易 还要有时间好好想想 大家看看这方法可行吗。

http://www.efile.com.cn/efile/dfw@97546/sss.rar
199行的
帮忙测试啊！

to eversun2000:
用递归 可能会很慢。

我发现计算好像不用时间，
时间花在画图上了。

圖論(二)—最短路徑及網路問題
最短路徑法(Shortest path algorithm)
&amp;#61548; 觀察：如果s,v1,v2,...,vi,..,vk是s到vk的最短路徑，則s,v1,v2,...,vi是s到vi的最短路徑。
&amp;#61548; 有四種狀況：
1. 所有的權重均為1。求s到其他所有點之最短路徑。
2. 所有的權重均為非負值(0或大於0)。求s到其他所有點之最短路徑。
3. 權重可以為負，但迴路之總權重不為負值。求s到其他所有點之最短路徑。
4. 任意二點之間的最短路徑。

&amp;#61548; 第一種情形(所有的權重均為1。求s到其他所有點之最短路徑。)
BFS (Breadth First Search), 複雜度：O(|E|)
Begin
Lable s with 0;
i &amp;#61612
0;
if &amp;#61476;an unlabeled node adjacent to a node labeled i then
begin
while &amp;#61476;an unlabeled node adjacent to a node labeled i do
begin
label this node i+1;
end_of_while;
i &amp;#61612
i+1;
go_to if_statement;
end_of_if;
end.

&amp;#61548; 第二種情形(所有的權重均為非負值，0或大於0。求s到其他所有點之最短路徑。)
Dijstra’s algorithm 複雜度：O(|V|2)
notation: &amp;#61548;(x)&amp;#61612;0, label x with 0
Begin
&amp;#61548;(s) &amp;#61612
0;
&amp;#61548;(v) &amp;#61612
&amp;#61559;, &amp;#61474;v&amp;#61625;s
/* &amp;#61559
代表無限大 */
T &amp;#61612
V

P &amp;#61612
&amp;#61638;;
u &amp;#61612
s;
Repeat
for each vertex v&amp;#61646;T adjacent to u do &amp;#61548;(v) &amp;#61612
min{&amp;#61548;(v), &amp;#61548;(u)+w(u,v)};
T &amp;#61612
T – {u};
P &amp;#61612
P&amp;#61640;{u};
u &amp;#61612
a new vertex in T with min. &amp;#61548;(u)

Until either (T = &amp;#61638 or (&amp;#61548;(u)= &amp;#61559;
end.
&amp;#61548; 第三種情形(權重可以為負，但迴路之總權重不為負值。求s到其他所有點之最短路徑。)
Bellman and Ford algorithm 複雜度：O(|V|&amp;#8226;|E|)
Umj = the length of a shortest path from s to j among all paths that contain at most m arcs.
=

Begin
m &amp;#61612
0;
U0s &amp;#61612
0;
U0j &amp;#61612
&amp;#61559;, for all j&amp;#61625;s
/* &amp;#61559;代表無限大 */
repeat
m &amp;#61612
m+1;
Umj&amp;#61612;Ujm-1, &amp;#61474;j, 1 &amp;#61603
j &amp;#61603
n;
for each arc(K,j) in G do
Umj = min{Ujm , UKm-1+w(K,j)};
until (Umj = Ujm-1) or (m = n) for &amp;#61474;j&amp;#61646;G;
IF (m = n) and (Umj&amp;#61625;Ujm-1) then output(“exist negative cycle!”)
end.

(例)

令Um = [Umj], j=1,2,3,4
U0 = [0, &amp;#61559;, &amp;#61559;, &amp;#61559;] /* &amp;#61559
代表無限大 */
U1 = [0, &amp;#61559;, 4, 10]
U2 = [0, 13, 4, 10] /* 13 = min(13,14) */
U3 = [0, 13, 4, 10]

&amp;#61548; 第四種情形(任意二點之間的最短路徑)
Floyd and Warshall algorithm 複雜度: O(N3)
Let the vertices be noted by 1,2,3...,n
Uki,j = 介於i,j之間的點編號最高為k時之總長度
Begin
U0ii &amp;#61612
0, &amp;#61474;i
U0ij &amp;#61612
w(i,j), &amp;#61474;(i,j)&amp;#61646;E
U0ij &amp;#61612
&amp;#61559;, &amp;#61474;(i,j)&amp;#61647;E /* &amp;#61559
代表無限大 */
for k=1 to n do
begin
for i=1 to n do
for j=1 to n do
Ukij &amp;#61612
min{Uijk-1, Uikk-1+ Ukjk-1}
end
end
end.

(例)














網路(network)
【定義】
網路(network)是一「加權有向圖」(weighted directed graph)，並具有以下之性質：
1. 網路上有二個特殊的點，分別稱之為「源點」(source)和「終點」(sink)。無任何連線(directed link/edge)指向源點；亦無任何連線由終點指向其它節點。源點可以提供無限大的流出量，終點可以容納無限大的流入量。
2. 每一個有向連線均有二個(屬性)權重：「容量」(capacity)與「流量」(flow)。一般而言，容量與流量均是非負數，且容量大於等於流量。
3. 各節點之總流入量等於總流出量(亦即，各節點無存量)。

網路流量問題(Network Flow Problem)
給予一個網路，求取由源點到終點的最大可能流量及路徑。

&amp;#61548; 求解「網路流量問題」，必須用到「最大流量等於最小切割定理」(max-flow min-cut theorem)。其演算法稱之為Ford &amp
Fulkerson algorithm。
&amp;#61548; Max-flow Min-cut theorem
For any network N, the maximum flow value is equal to the minimum capacity of an s-t cut.
&amp;#61548; the labeling algorithm (Ford &amp
Fulkerson algorithm)
Begin
f(i,j) &amp;#61612
0, &amp;#61474;(i,j) &amp;#61646;E
/*any feasible flow = 0 */
&amp;#61548;(s) &amp;#61612
(-,&amp;#61559
/* assign the initial label to s , where &amp;#61559
represents infinity*/
repeat
/* search for an augmenting path
initially, s is the only vertex that is labeled but unscanned. */
while there is a labeled but unscanned node i do
begin /*scanning i */
for each unlabeled j such that f(i,j) < c(i,j) do
/* forward labeling from i */
&amp;#61540;j &amp;#61612
c(i,j) – f(i,j);
&amp;#61548;(j) &amp;#61612
(i+,&amp;#61540;j);
for each unlabeled j such that f(j,i)>0 do
/* reverse labeling from i */
&amp;#61540;j &amp;#61612
f(j,i);
&amp;#61548;(j) &amp;#61612
(i-,&amp;#61540;j);
mark i “scanned”;
end_of_while;
if t is labeled then do /* flow augmentation */
begin
&amp;#61540
&amp;#61612
min{&amp;#61540;j | j&amp;#61646;V(G) };
increase or decrease a flow of &amp;#61540
units along each arc of the augmenting path according to +, - sign;
erase all scanning mark;
erase all labels except &amp;#61548;(s);
end;
until you are not able to label t;
identify the minimum cut
/* edges from labeled nodes to unlabeled nodes */
end.

最大和最小都一样；都是你想要的最值；文中讲最短也就是最有价值的；
&amp;#61548; 觀察：如果s,v1,v2,...,vi,..,vk是s到vk的最有价值的路徑，則s,v1,v2,...,vi是s到vi的最有价值的路徑。

用深度搜索遍历

无聊,一个三元数组就能解决..

第一元记录价值,第二元记录该点到出口的MAX价值,第三元记录它所指的下一个节点(
用1表示左用0表示右)..然后用出口倒算回入口.经典的动态规划..

三元数组解决？近兄台的理解，为什么不用9元数组呢？
说笑了[]

http://www.efile.com.cn/efile/dfw@97546/sss.rar
199行那个按钮。

ps:
我已经给出了源吗？
为什么 每人看？