旅 行明天就要和所有M&F成员去唐山旅游了,但是SF面馆特派员还有N件事情没有做完,做这些事情还有M个限制条件,每个限制条件均为:事件A必须在事件B之前完成。现在SF面馆特派员想知道,他做完这N件事一共有多少种方法。
Input
第一行,两个整数N、M。
接下来M行,每行两个数Ai、Bi,表示事件Ai必须在事件Bi之前完成。
Output
一个整数,表示做完这N件事一共有多少种方法。
样例
Input
3 2
1 3
2 3
Output
2
数据范围
N<=17;
M<=400。======================================================================================
这里便是求有限制的方案安排的方案数,如果单求一个可求方案可以用拓扑排序。拓扑排序的想法就是每一次找一个入度为0的节点,将之加入已选的点的集合中,然后在把所有和它相连的点的入度都减去1,然后再重复这个过程。
过程简写一下就是:
dfs(u);
v[u]:=true;
for i:=1 to n do
if(not v[i])and(g[u,i]=1)then dec(ru[i]);
for i:=1 to n do
if ru[i] then begin
inc(tot);
q[tot]:=i;
dfs(i);
break;
end;
最后答案就保存在q数组里面。
然后求拓扑排序的方案数,求方案数往往就用到两种方法,一种叫搜,一种叫推。
这里的数据范围太小了,用搜明显可过,即每一次搜到一个正解加1后就立即回溯,再去枚举其他可能的点。回溯的时候需要把这次改动的点的信息重新标记回来。其余的也就没什么了。
program tour;
var
a:array[1..17,1..17]of longint;
ru:array[1..17]of longint;
f:array[1..17]of longint;
vi:array[1..17]of boolean;
n,m:longint;
function dfs(u:longint):longint;
var i:longint;
p:longint;
f:boolean;
v:array[1..17]of boolean;
begin
f:=true;
for i:=1 to n do
if (i<>u)and(not vi[i])then begin
f:=false;
break;
end;
if f then exit(1);
vi[u]:=true;
fillchar(v,sizeof(v),false);
p:=0;
for i:=1 to n do
if a[u,i]=1 then
begin
dec(ru[i]);
v[i]:=true;
end;
for i:=1 to n do
if (not vi[i])and(ru[i]=0) then p:=p+dfs(i);
for i:=1 to n do
if v[i] then inc(ru[i]);
vi[u]:=false;
exit(p);
end;
procedure main;
var i:longint;
ans:longint;
begin
ans:=0;
for i:=1 to n do
if ru[i]=0 then
begin
fillchar(vi,sizeof(vi),false);
ans:=ans+dfs(i);
end;
write(ans);
end;
procedure init;
var i,x,y:longint;
begin
read(n);
read(m);
fillchar(ru,sizeof(ru),0);
for i:=1 to m do
begin
read(x);read(y);
a[x,y]:=1;
inc(ru[y]);
end;
end;
begin
init;
main;
end.
评论