路径问题（c语言）
寻找最有价值路径（c语言）
描述：
从上（入口）往下行走，直到最下节点（出口）结束，将所经节点上的数值相加，要求找到一条最有价值路径（既是路径总数值最大）并输出总数值。
图：
入口 ↓
③
/\
⑤ ④
/ \ / \
① ② ⑤
\ / \ /
⑨ ⑧
\ /
③
出口 ↓
输入文件：（abc.in)
第一行只有一个数n(1<=n<=199),且n为奇数，说明节点的层。从第二行到底n+1行为每一层中各节点的数值（在0和100之间），各个数用空格隔开，输入不要求判错。
输出文件：（abc.out)
只有一个数，为所求路径的价值数。
例子：
输入文件内容：
5
3
5 4
1 2 5
9 8
3
输出文件内容：
23
问题点数：100、回复次数：28Top
1 楼kbsoft（让世界充满爱!）回复于 2002-03-05 17:47:05 得分 0
这是求最长路径的题目嘛
Top
2 楼kbsoft（让世界充满爱!）回复于 2002-03-05 18:01:58 得分 5
以下为求一个有向无环图中最长的路径的算法，其它的问题你可以自行写出
int maxlen,path[MAXSIZE]; //数组path用于存储当前路径
int mlp[MAXSIZE]; //数组mlp用于存储已发现的最长路径
void Get_Longest_Path(ALGraph G{
maxlen=0;
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++) visited[j]=0;
if(!indegree[i]) DFS(G,i,0);//从每一个零入度结点开始深度优先遍历
}
printf("Longest Path:");
for(i=0;mlp[i];i++) printf("%d",mlp[i]); //输出最长路径
}//Get_Longest_Path
void DFS(ALGraph G,int i,int len)
{
visited[i]=1;
path[len]=i;
if(len>maxlen&&!G.vertices[i].firstarc) //新的最长路径
{
for(j=0;j<=len;j++) mlp[j]=path[j]; //保存下来
maxlen=len;
}
else
{
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
j=p->adjvex;
if(!visited[j]) DFS(G,j,len+1);
}
}//else
path[i]=0;
visited[i]=0;
}//DFS
Top
3 楼birdinfly（birdinfly）回复于 2002-03-05 18:19:20 得分 0
可以看看运筹学,里面对这类问题讲的很深刻.Top
4 楼darkwowowo（黑暗中呼啸）回复于 2002-03-05 18:44:37 得分 0
看看例子，好像是每一层只能经过一次，否则的话，就不只23了。
还有，你帮我用tc作一下吧，顺便在加多点注释，那个输入也不好弄，因为每一行都要区分。^_^Top
5 楼sticker（了了）回复于 2002-03-05 19:37:02 得分 0
《数据结构》里尽是讲这种题的。Top
6 楼darkwowowo（黑暗中呼啸）回复于 2002-03-05 19:49:12 得分 0
谁帮我写一下啊？？？！！！Top
7 楼darkwowowo（黑暗中呼啸）回复于 2002-03-05 20:37:34 得分 0
有谁帮帮我啊？写个tc代码吧，各位老大。Top
8 楼LLnju（LLnju）回复于 2002-03-05 21:47:19 得分 90
to darkwowowo:
你怎么一下问了这么多的问题，是不是老师布置的作业，什么问题都应该自己先想想，实在有什么不清楚了才来问问，这才是个办法。不要一出来就让人写代码，这样不好，有人告诉了你思路，程序最好还是自己写，不然 ......。
看你这个问题 "c或c++的输入输出问题" 实在是应该自己去看书。
这个问题 "超大整数开方问题（c语言)" 你至少应该先想想大概会用到些什么东东的，不要一出来就问人要代码。
在看看你的这个问题，就知道你根本没有想过这个问题，你这个问题中那个 图 的结构实在是简单了一些，用不着 kbsoft 写的 DFS ，你看看这个东西：
an1 an2 .... ann
an'1 an'2 an'3 .... an'n
如果 已知 上面一层的最长路径了，下面一层的应该会吧 ，像 f(an'1) = f(an1)+an1 , f(an'2) = max( f(an1)+an1 , f(an2)+an2) ) ..... , 这样一看就知道是个最标准的递归问题了。有了上面的就可以解决像：
a11
a21 a22
a31 a32 a33
...................
an1 an2 ............. ann
这样的图形了，你把下面的图翻过来，也是这样的一个图，不翻过来也可以用类似的想法处理，这样一来就简单了吧。
输入输出的问题最好不要问，自己看书解决吧，用 C 就注意 scanf,fscanf , sscanf , 用 C++ 就更简单 ，用熟 istream , istringstring , istrstream 就行了。Top
9 楼LLnju（LLnju）回复于 2002-03-05 21:53:47 得分 0
还有不要用 tc 了，用c/c++的话还是用 gcc , vc.net , vc , bcb 吧，不然别人写的代码，你大概是不能通过的。Top
10 楼stoneyrh（）回复于 2002-03-05 21:59:25 得分 0
高人一大堆，我还要继续努力Top
11 楼darkwowowo（黑暗中呼啸）回复于 2002-03-05 22:46:15 得分 0
我的思路是这样的，关于这个图的，首先要求是最短的路径，而且权值要最大，那肯定一层只能走一次（也必须走一次，否则无法到最下一层），那我是不是要把所有的路径找出来，再比较权值？这样计算量是不是太大了，不过好像算法简单一点，只要每找出一条路径，就把权值比较一次，最后最大的就是结果，还是有别的好方法？Top
12 楼darkwowowo（黑暗中呼啸）回复于 2002-03-05 22:55:51 得分 0
那这样，我每到一个节点，就把当前走过的路径权值算一下，只保留最大的全值的路径，这样可以减少运算次数。这样，其实每个节点最多只要比较两次，就是它左上方的和右上方的节点的权值与走过路径权值，把大的留下。可是就是写不出来。Top
13 楼sin4x（一瓶水）回复于 2002-03-05 23:21:13 得分 0
深度搜索，用一个全局的数组记录目前为止最有价值的
每次到最底的时候与其比较，更有价值则替换，
1<n<100的话，就这样应该就没问题了Top
14 楼LLnju（LLnju）回复于 2002-03-06 09:23:28 得分 0
不用DFS,看看上面的图怎么样求解。对上面的节点编号为:
a11
a21 a22
a31 a32 a33
a41 a42
a51
oo
记 f(x) 为 a11 到 x 的最长路径,不包括自己本身。
首先 : f(a11) = 0. f(a21)=f(a22)=a11=3.
f(a31)=f(a21)+a21=8. f(a32)=max( f(a21)+a21 , f(a22)+a22 ) = 8. f(a33) = f(a22)+a22 = 7.
f(a41)=max(f(a31)+a31,f(a32)+a32 ) = 10. f(a42)=max(f(a32)+a32,f(a33)+a33)=12
f(a51)=max(f(a41)+a41,f(a42)+a42)=20
F = f(a51)+a51 = 23
用这种算法，算到1000层也没有问题，用 DFS 的话，50层就够呛。Top
15 楼darkwowowo（黑暗中呼啸）回复于 2002-03-06 10:19:17 得分 0
LLnju(LLnju)你说得很对，这种算法算到1000层也没问题，可是我要把它写出来就是写不出，给我写一段吧Top
16 楼starfish（海星）回复于 2002-03-06 17:22:13 得分 0
这种分层次的图的路径问题，可以用动态规划解决Top
17 楼Justin（兰色梧桐）回复于 2002-03-06 17:33:53 得分 5
给你个动态规划的源码：
/*
* File: longest.c
* Desciption: 动态规划算法计算网络的最长路线和最短路线
* Created: 2001/12/2
* Author: Justin Hou [mailto:justin_hou@hotmail.com]
*
*/
#include <stdio.h>
#define N 7 /* 顶点数目 */
#define I 999 /* 表示无穷大 */
int graph[N][N] = { /* 图的邻接矩阵 */
{I, 4, 5, 8, I, I, I},
{I, I, I, 6, 6, I, I},
{I, I, I, 5, I, 7, I},
{I, I, I, I, 8, 9, 9},
{I, I, I, I, I, I, 5},
{I, I, I, I, I, I, 4},
{I, I, I, I, I, I, I}
};
int List[N]; /* 存放拓扑序列 */
int TopologicalOrder(); /* 拓扑排序函数 */
void main() /* 主 函 数 */
{
int i, j, k, l;
int ee[N], el[N]; /* 最长最短距离 */
int path_e[N][N], path_l[N][N], n_e[N], n_l[N];
/* 记录路径数据 */
/* 初始化数据 */
for (i = 0; i < N; i++) {
n_e[i] = 0; /* 到 i 的最短路线的结点数 */
n_l[i] = 0; /* 到 i 的最长路线的结点数 */
ee[i] = I;
el[i] = 0;
}
ee[0] = el[0] = 0; /* 初始化头结点 */
path_e[0][0] = 0;
path_l[0][0] = 0;
n_e[0] = 1;
n_l[0] = 1;
/* 拓扑排序 */
if (!TopologicalOrder())
return;
/* 对于拓扑序列,运用动态规划步步算出最长路线与最短路线 */
for (i = 0; i < N; i++) {
/* 提取拓扑序列的元素 */
k = List[i];
/* 更新它所指向顶点的所有数据 */
for (j = 0; j < N; j++) {
/* 寻找指向的顶点 */
if (graph[k][j] != I) {
/* 如果新路径更短 */
if (graph[k][j] + ee[k] < ee[j]) {
/* 更新最短路径长度 */
ee[j] = graph[k][j] + ee[k];
/* 更新最短路线 */
for (l = 0; l < n_e[k]; l++) {
path_e[j][l] = path_e[k][l];
}
path_e[j][l] = j;
n_e[j] = l + 1;
}
/* 如果新路径更长 */
if (graph[k][j] + el[k] > el[j]) {
/* 更新最长路径长度 */
el[j] = graph[k][j] + el[k];
/* 更新最长路线 */
for (l = 0; l < n_l[k]; l++) {
path_l[j][l] = path_l[k][l];
}
path_l[j][l] = j;
n_l[j] = l + 1;
}
}
}
}
/* 输出结果到屏幕 */
for (i = 0; i < N; i++) {
printf("shortest(%d): %2d Path: ", i + 1, ee[i]);
for (j = 0; j < n_e[i]; j++) {
printf("%d ", path_e[i][j] + 1);
}
printf("\n");
printf("longest (%d): %2d Path: ", i + 1, el[i]);
for (j = 0; j < n_l[i]; j++) {
printf("%d ", path_l[i][j] + 1);
}
printf("\n");
}
}
int TopologicalOrder()
{
int i, j, top, count;
int indegree[N], Stack[N];
top = 0; /* 栈顶标志 */
for (i = 0; i < N; i++) {
indegree[i] = 0; /* 初始化入度 */
for (j = 0; j < N; j++) {
if (graph[j][i] != I) { /* 如连通 */
indegree[i]++; /* 入度自增1 */
}
}
if (!indegree[i]){ /* 如入度为零 */
Stack[top++] = i; /* 入栈 */
}
}
count = 0; /* 输出顶点数 */
while (top != 0) {
i = Stack[--top];
List[count++] = i;
for (j = 0; j < N; j++) {
if (graph[i][j] != I) { /* 如连通 */
if (!(--indegree[j])) { /* 而且入度为零 */
Stack[top++] = j; /* 入栈 */
}
}
}/* for */
}/* while */
return (count < N) ? 0 : 1;
}
Top
18 楼hssfox（）回复于 2002-03-06 21:28:34 得分 0
kkTop
19 楼cntiger（阿汤）回复于 2002-03-07 10:53:01 得分 0
wonderfulTop
20 楼darkwowowo（黑暗中呼啸）回复于 2002-03-07 11:57:28 得分 0
还没看明白，正在琢磨。Top
21 楼cxwhust（）回复于 2002-03-07 16:48:56 得分 0
我粗略看了一下，觉得解决方案基本上都是穷举法，显然受节点数量限制太大。有没有哪位老兄接触过“中国邮递员问题”？能否计算100个节点左右的最短路径呢？如有，请指教！先谢啦！Top
22 楼wgku（云霄）回复于 2002-03-07 18:58:11 得分 0
哇。。。。。。。。我还没看懂Top
23 楼LLnju（LLnju）回复于 2002-03-08 09:16:45 得分 0
给你一个可以直接运行的，O(n^2), 算到5000 层应该没有问题，呵呵。
#pragma warning(disable:4786)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cassert>
#include <ctime>
#include <string>
#include <set>
using namespace std;
template<typename _Ty>
const _Ty STDMAX( const _Ty& __a , const _Ty& __b ){
return __a >= __b ? __a : __b; }
typedef pair<int,int> dtvalpair;
typedef vector<dtvalpair> laydt;
typedef vector<laydt> graphdt;
class pathInfo
{
size_t depth;
graphdt graph;
public:
pathInfo() : depth(0) {}
pathInfo( size_t dep ) { init(dep); };
void init( size_t dep );
public:
laydt& operator[] ( size_t index )
{
assert( index < depth );
return graph[index];
}
const laydt& operator[]( size_t index ) const
{
assert( index < depth );
return graph[index];
}
public:
void rand()
{
srand( static_cast<unsigned>( time(NULL) ) );
size_t mx = ( depth + 1 ) / 2;
for( int i = 0; i < mx; ++i )
for( int j = 0; j <= i; ++j )
graph[i][j] = dtvalpair( ::rand() % 100 , 0 );
for( i = mx; i < depth; ++i )
for( int j = 0; j < depth - i; ++j )
graph[i][j] = dtvalpair( ::rand() % 100 , 0 );
}
void show( ostream& os ) const
{
size_t mx = ( depth + 1 ) / 2;
for( int i = 0; i < mx; ++i ){
for( int j = 0; j <= i; ++j ) {
os << graph[i][j].first<<'('<<graph[i][j].second<<")\t"; }
os << endl; }
for( i = mx; i < depth; ++i ){
for( int j = 0; j < depth - i; ++j ){
os << graph[i][j].first<<'('<<graph[i][j].second<<")\t"; }
os << endl; }
}
void dump( ostream& os ) //! 记录了求解过程，格式也符合输入文件的要求.
{
os << depth << endl << endl;
size_t mx = ( depth + 1 ) / 2;
for( int i = 0; i < mx; ++i ){
for( int j = 0; j <= i; ++j ) {
os << graph[i][j].first<< '\t'; }
os << endl; }
for( i = mx; i < depth; ++i ){
for( int j = 0; j < depth - i; ++j ){
os << graph[i][j].first<< '\t'; }
os << endl; }
os << endl << endl << "DUMP INFO:" << endl;
int val = getValue(); show( os );
os << endl << endl << "VAL:" << val << endl;
}
public:
int getValue()
{
size_t mx = ( depth + 1 ) / 2;
graph[0][0].second = 0;
for( int i = 1; i < mx; ++i ){
graph[i][0].second = graph[i-1][0].first + graph[i-1][0].second;
for( int j = 1; j <= i - 1; ++j ) {
graph[i][j].second = STDMAX( graph[i-1][j-1].second + graph[i-1][j-1].first ,
graph[i-1][j].second + graph[i-1][j].first ); }
graph[i][i].second = graph[i-1][i-1].first + graph[i-1][i-1].second; }
for( i = mx; i < depth; ++i )
for( int j = 0; j < depth - i; ++j )
graph[i][j].second = STDMAX( graph[i-1][j].second + graph[i-1][j].first ,
graph[i-1][j+1].second + graph[i-1][j+1].first );
return graph[depth-1][0].first + graph[depth-1][0].second;
}
public:
friend ostream& operator << ( ostream& os , pathInfo& pi ) {
return os << pi.getValue(); }
friend istream& operator >> ( istream& is , pathInfo& pi ) {
size_t dep; is >> dep; pi.init( dep ); int dt;
assert( dep >= 3 && dep & 1 );
size_t mx = ( pi.depth + 1 ) / 2;
for( int i = 0; i < mx; ++i )
for( int j = 0; j <= i; ++j ) {
is >> dt; pi[i][j] = dtvalpair( dt , 0 ); }
for( i = mx; i < pi.depth; ++i )
for( int j = 0; j < pi.depth - i; ++j ) {
is >> dt; pi[i][j] = dtvalpair( dt , 0 ); }
return is;
}
};
void pathInfo::init( size_t dep )
{
depth = dep;
graph.resize( dep );
assert( dep & 1 && dep >= 3 );
for( int i = 0; i < dep; ++i )
graph[i].resize( ( dep + 1 ) / 2 );
}
void test()
{
ofstream dumpDt("src.txt");
pathInfo pi(999);
pi.rand(); pi.dump( dumpDt );
}
void main()
{
try {
cout << "TEST pathInfo BEGIN ......" << endl;
test(); //!
cout << "TEST pathInfo END ......" << endl;
pathInfo pi;
cout << "Input filename:";
string strFn; cin >> strFn;
ifstream is( strFn.c_str() );
is >> pi;
cout << "VAL:" << pi << endl;
}
catch(...)
{
cerr << "FATAL ERROR" << endl;
}
}Top
24 楼darkwowowo（黑暗中呼啸）回复于 2002-03-08 10:07:47 得分 0
LLnju(LLnju),谢谢你了，能给我加点注释吗？我重新开个贴子，ok?还有那个开方的问题，帮帮忙吧，星期一早上就要交了，而我实在是想不出来啊。我现在身边的数值分析的书又没有，你帮我一下啦，我还剩几百分，如果要分的话都给你了，要不然，就当我欠你啦。我的算法真的很不行。Top
25 楼darkwowowo（黑暗中呼啸）回复于 2002-03-08 10:29:16 得分 0
我在c/c++版里另外开个贴子了Top
26 楼airwjd（Nigle）回复于 2002-03-09 19:04:38 得分 0
收藏。Top
27 楼shajie（笨鸟先飞）回复于 2002-03-10 18:14:32 得分 0
这个问题太简单了！
Top
28 楼LeeMaRS（小菜虎，仍需努力）回复于 2002-03-12 00:23:07 得分 0
LLnju 能介绍一下你的算法么? 动态规划?Top
