动态规划-航线设置

program dongtai;  {动态规划之友好城市航线设置问题}
var
 d:array[1..1000,1..4] of integer;
 i,j,k,n,L,p:integer;

 procedure print(L:integer);  {打印结果}
 begin
 writeLn('最多可设置的航线数是 : ',k);
 repeat
 writeLn(d[L,1]:4,d[L,2]:4);  {输出可以设置航线的友好城市代码}
 L:=d[L,4]
 untiL L=0
 end;

begin
 writeLn('输入友好城市对数: ');
 readLn(n);
 writeLn('输入友好城市对（友好城市放在同一行:');  {输入}
  for i:=1 to n  do
 readLn(d[i,1],d[i,2]);  {D[I，1]表示起点，D[I，2]表示终点}
  for i:=1 to n  do
 begin
 d[i,3]:=1;  {D[I，3]表示可以设置的航线条数}
 d[i,4]:=0  {D[I，4]表示后继，即下一条航线从哪里开始设置，为0表示不能设置下一条航线}
 end;
for i:=n-1 downto 1  do  {从倒数第二个城市开始规划}
 begin
 L:=0; p:=0;  {L表示本城市后面可以设置的航线数，P表示下条航线从哪个城市开始}
  for j:=i+1 to n  do  {找出本城市后面可以设置的最大航线数和小条航线到底从哪个城市开始设置}
  if (d[i,2] L) then 
  {如果本城市I的终点小于后面城市的终点（即不相交）}  {并且此城市后面可以设置的航线数大于L}
 begin
 L:=d[j,3];  {那么L等于城市J的可以设置航线数}
 p:=j  {P等于可以设置下条航线的城市代码}
 end;
  if L>0 then  {如果本城市后面总共可以设置的航线数>0则}
 begin
 d[i,3]:=L+1;  {本城市可以设置的航线数在下个城市可以设置航线数的基础上加1}
 d[i,4]:=p  {D[I，4]等于本城市后续城市的代码}
 end
 end;
 k:=d[1,3];  {K为可以设置最大航线数，假设初值为第一个城市可以设置的航线数}
 L:=1;  {L为城市代码，初值为第一个城市}
  for i:=2 to n  do  {找出可以设置航线的最大值，赋值给K，同时L记下哪个可以设置最大航线数的城市代码}
  if d[i,3]>k then
 begin
 k:=d[i,3];
 L:=i
 end;
  for i:=1 to n  do  {打印结果，因为有可能有多种方案，所以只要哪个城市可以设置的航线数等于最大值K就打印结果}
  if d[i,3]=k then print(i)

end.