1.????????題目

樹形圖計數(shù)

count.pas/c/cpp

?

【問題描述】

小k同學(xué)最近正在研究最小樹形圖問題。所謂樹形圖，是指有向圖的一棵有根的生成樹，其中樹的每一條邊的指向恰好都是從根指向葉結(jié)點(diǎn)的方向。現(xiàn)在小k在紙上畫了一個圖，他想讓你幫忙數(shù)一下這個圖有多少棵樹形圖。

?

【輸入格式】

第1行輸入1個正整數(shù)：n，表示圖中點(diǎn)的個數(shù)

第2~n+1行每行輸入n個字符，描述了這個圖的鄰接矩陣。第i+1行第j個字符如果是0則表示沒有從i連向j的有向邊，1表示有一條從i到j的有向邊。

?

【輸出格式】

輸出1行1個整數(shù)，表示這個有向圖的樹形圖個數(shù)。

?

【樣例輸入】

count.in

4

0100

0010

0001

1000

?

【樣例輸出】

count.out

4

?

【數(shù)據(jù)規(guī)模和約定】

對于100%的數(shù)據(jù)，n<=8?.

2.????????算法

以每一個節(jié)點(diǎn)為根，判斷從這個根開始用有向邊能不能找到所有節(jié)點(diǎn)，如果能則記錄。

?

判斷方法：首先將這棵樹構(gòu)建出來，也就是輪流將該點(diǎn)的入度所連的點(diǎn)作為他的父親節(jié)點(diǎn)，看可不可以將這棵樹構(gòu)建出來，如果可以，再看構(gòu)建出來的樹能不能找到所有節(jié)點(diǎn)。

3.????????注意事項(xiàng)

要先將這棵樹構(gòu)建出來，再判斷。

4.????????代碼

深搜+判斷（ASDF）

program?asdf;

??var

????b,a:array[0..10,0..10]of?longint;

????f,ff:array[0..10]of?boolean;

????fa:array[0..10]of?longint;

????n,i,j,k,root:longint;

????all,sum,ans:qword;

????flag:boolean;

????ch:char;

??function?judge:boolean;

????var

??????i,x:longint;

????begin

??????fillchar(f,sizeof(f),false);

??????f[root]:=true;

??????for?i:=1?to?n?do

????????begin

??????????fillchar(ff,sizeof(ff),false);

??????????x:=fa[i];

??????????while?(fa[x]<>root)and(not?f[fa[x]])and(fa[x]<>0)?do

????????????begin

??????????????if?ff[x]?then?exit(false);

??????????????ff[x]:=true;

??????????????x:=fa[x];

????????????end;

??????????if?fa[x]=0?then?exit(false);

??????????if?(fa[x]=root)or(f[fa[x]])?then

????????????begin

??????????????x:=i;

??????????????while?not?f[x]?do

????????????????begin

??????????????????f[x]:=true;

??????????????????x:=fa[x];

????????????????end;

????????????end;

????????end;

??????exit(true);

????end;

??procedure?dfs(x:longint);

????var

??????i:longint;

????begin

??????if?x=root?then

????????begin

??????????dfs(x+1);

??????????exit;

????????end;

??????if?x=n+1?then

????????begin

??????????if?judge?then?inc(ans);

??????????exit;

????????end;

??????for?i:=1?to?n?do

????????if?b[i,x]<>0?then

??????????begin

????????????fa[x]:=i;

????????????dfs(x+1);

??????????end;

????end;

??begin

????assign(input,'count.in');reset(input);

????assign(output,'count.out');rewrite(output);

????readln(n);

????for?i:=1?to?n?do

??????begin

????????for?j:=1?to?n?do

??????????begin

????????????read(ch);

????????????if?ch='1'?then?b[i,j]:=1

????????????else?b[i,j]:=0;

??????????end;

????????readln;

??????end;

????for?root:=1?to?n?do

??????begin

????????flag:=false;

????????for?i:=1?to?n?do

??????????if?b[root,i]<>0?then

????????????begin

??????????????flag:=true;

??????????????break;

????????????end;

????????fa[root]:=root;

????????if?flag?then

??????????dfs(1);

??????end;

????write(ans);

????close(input);

????close(output);?

??end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/SueMiller/archive/2011/10/15/2213100.html

總結(jié)

以上是生活随笔為你收集整理的解题报告 树形图计数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。