这是npq问题，算法是拓扑排序
以下代码及注释均由本人完成，如有错误或欠佳之处，请发邮件给我：
wc_111191@sina.com（楼下提供测试数据）
——————————————————————————————————————
{npq问题(拓扑排序)}
Program npq;
Const
inf = 'npq.in';
ouf = 'npq.out'; //定义输入输出文件
Type
Node = ^Rec;
Rec = Record
Info: Integer;
Next: Node;
End; //定义链表结构
Var
map: Array[0..100]Of Node; //邻接表
le, rd, a, b: Array[0..100]Of Integer;
{le存储邻接表数组中每个链表的长度,即当前结点出度的个数,
rd存储当前节点入度的个数,a存放拓扑排序的结果,b
表示从
0~第i个数的部分和}
n, p, q, i, count, now, sum, j: Integer;
//count表示入度为0的结点的个数，sum是已经完成多少个结点
//now表示当前正在进行拓扑排序的入度为零的结点的序号
Procedure No;
Begin
WriteLn('No');
Close(Input);
Close(Output);
Halt;
End; //如果无解，则输出'NO'
Procedure Inse(i, j: Integer); //此过程是将i点连向j点
Var
k, Temp: Node; //k是待修改的元素，temp是活动在链表中的指针
l: Integer;
Begin
New(k);
k^.Info := j;
Temp := Map;
Inc(le);
Inc(rd[j]);
For l:=1 To le Do Begin
If l = le Then Temp^ := k^
Else Begin
If l = le - 1 Then New(Temp^.next);
Temp := Temp^.Next;
End;
End;
End;
Procedure KillNode(i: Integer); //删除结点和与之相连的边
Var
j: Integer;
Temp: Node;
Begin
If (le = 0)And(Sum <> n) Then No;
Inc(sum);
Temp := Map;
For j:=1 To le Do Begin
Dec(rd[Temp^.Info]);
Temp := Temp^.Next;
End; //减小与之相连的边的入度个数
rd := -1; //为了避免被误判为入度为零
Map := Nil; //删除对应的链表
a[sum] := i; //记录结果
le := 0; //出度为0
End;
Begin
Assign(Input, inf);
Assign(Output, ouf);
Reset(Input);
Rewrite(Output); //打开文件
ReadLn(n, p, q); //输入n, p, q
For i:=0 To n Do New(Map); //新建指针
For i:=n Downto q Do
Inse(i, i - q); //在k和k-q之间画有向弧
For i:=0 To n - p Do
Inse(i, i + p); //在k和k+q之间画有向弧
For i:=0 To n Do Begin
Count := 0;
For j:=0 To n Do
If rd[j] = 0 Then Begin
Inc(Count);
Now := j;
End;
If Count <> 1 Then No;
KillNode(Now);
End; //拓扑排序
For i:=1 To n + 1 Do
b[a] := i - 1; //根据结果创建b数组
For i:=1 To n Do
Write(b - b[i - 1], ' '); //根据部分和输出结果
WriteLn;
Close(Input);
Close(Output); //关闭文件
End.[ 此贴被wc_111191在2007-12-10 22:55重新编辑 ]
