注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【没检测..】【拓扑排序加搜】【旅行】  

2013-07-30 10:36:54|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   

明天就要和所有M&F成员去唐山旅游了,但是SF面馆特派员还有N件事情没有做完,做这些事情还有M个限制条件,每个限制条件均为:事件A必须在事件B之前完成。现在SF面馆特派员想知道,他做完这N件事一共有多少种方法。
Input
第一行,两个整数NM
接下来M行,每行两个数AiBi,表示事件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.


  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018