pascal catch

来源:百度知道 编辑:UC知道 时间:2024/06/16 02:13:05
5、拦截匪徒(catch)
问题描述:某市的地图是一个由n个点组成的无向图,每个点代表一个区。现在第p区发生了抢劫案,而警察为了截住匪徒埋伏在一个匪徒必经的区域。由于不知道匪徒会向哪个区域逃窜,局长要求身为警察局电脑专家的你计算出对于任意一个匪徒可能逃向的区j,找出一个可以截住匪徒的区k,即匪徒从p区逃向j区,必经过k区。由于地区j可能为匪徒的老巢所在,所以局长希望在路上拦住匪徒,而不是在j区抓捕。

输入格式(catch.in):
第一行为n,p(1≤p≤n≤100)。
接下来为n*n的矩阵A,A[i,j]=1表示i区和j区有路相连,反之为0。

输出格式(catch.out):
输出n-1行,按顺序从j=1,2,……,n依次输出对于每一个j,警察可以在哪些点埋伏。如有多个点,则要按照从小到大的顺序依次输出;如没有,则对应行输出“NO”。

样例:
输入:
5 1
0 1 1 0 0
1 0 1 1 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 0

输出:
NO
NO
2
2 4

请用pascal语言编写程序。
急需。。。。。
希望各位懂点编程的高手们都来帮帮忙!

能给个程序参考一下吗?
还有,能有解题报告就更好了!

我觉得ls的算法有问题。。。

我认为是这样:枚举每个点,将这个点删去,然后从p点遍历,看有那些点不能到达...复杂度O(n^3)..不过够了...
下面程序不保证对。。。(貌似就是错的。。没有预处理初始不连通。。lz自己搞把。。。)
var
a:array[0..100,0..100]of boolean;
b:array[1..100]of boolean;
l:array[1..100]of integer;
ans:array[0..100,0..100]of integer;
i,j,k,n,p,x:integer;
procedure dfs(x:integer);
var i:integer;
begin
b[x]:=true;
for i:=1 to n do if a[x,i]and(not b[i])and(i<>k)then dfs(i);
end;
begin
assign(input,'catch.in');reset(input);
assign(output,'catch.out');rewrite(output);
readln(n,p);
for i:=1 to n do
for j:=1 to n do begin
read(x);
if x>0 then a[i,j]:=true;
end;
for k:=1 to n do if k<>p then begin
fillchar(b,sizeof(b),0);
dfs(p); b[k]:=true;
for i:=1 to n do if not b[i] then begin
inc(l[i]);
ans[i,l[i]]:=k;
end;