图论

航空路线问题

题目描述

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 (1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。 (2)除起点城市外,任何城市只能访问 1 次。 对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。 (更多…)

DefFrancis
图论

方格取数加强版

题目描述

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大 (更多…)

DefFrancis