这一道题目中拓扑序列指的是一层一层去的,类似于noip pj no.4的样子,强调的是等级制,层次制,因此1,2是同一层次,3和4是又一层次,所以上述②③不成立。
@[url=/usershow?uid=1]kkksc03[/url] 在题目中把“这一道题目中拓扑序列指的是一层一层去的,类似于noip pj no.4的样子,强调的是等级制,层次制,”加进去,以免误导
by lych @ 2014-01-23 20:25:10
@[url=/usershow?uid=734]lych[/url] 至少百度上的没有
by 点击获取“V”认证 @ 2014-01-23 21:14:42
@[url=/usershow?uid=734]lych[/url] 根据维基百科:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。
所以说楼主的例子是符合拓扑排序的要求的。
我也没有理解你所说的“层次”。所以希望要么改下数据,要么再说清楚点,为什么类似楼主的例子1、2在3、4的前面。
by kkksc03 @ 2014-01-23 21:36:13
可能还是我理解的问题。其实本来想出的是按照动态规划那样,比如说第一阶段有几个点,那么如果是按照动态规划的思路的话,显然是先处理好了1,2然后再处理3,4的,那么根据乘法原理,当然是4种。可能题目描述不太好,因为我看这个跟拓扑排序很像,所以才起名的。那么为了方便理解,还是改一下数据吧。主要是考虑到,如果真的向未泱说的那样,也就是求拓扑序列总数的话,可能对于“海选第1轮”的难度不符了。程序还是能写的,但是复杂度就略高了。
by lych @ 2014-01-24 13:17:05
「嗯」 可以不考虑状压DP的呀。。。
对于拓扑下DFS计数也可以过的说。。
by usqwedf @ 2014-01-26 20:46:22
另外 -> 刚开始 图论 好像有点难度过大了。。。
假使有些小朋友和我一样不会很惨么。。。
可以考虑下冷门算法 -> ->
我想太多了。。「面壁熊」
by usqwedf @ 2014-01-26 20:49:14
@[url=/usershow?uid=69]usqwedf[/url]
by vip999 @ 2014-01-28 14:01:08
@vip999
那仅仅是贴吧里的「气泡熊」。。。
by usqwedf @ 2014-01-28 14:40:16
@lych
@vip999
by usqwedf @ 2014-01-28 14:41:44
```cpp
#include<cstdio>
#include<cstring>
const int maan=11;
int n;
int d[maan][maan],R[maan];
bool vis[maan];
int dfs(int a,int depth)
{
if(depth==n)return 1;
int i,sum=0;
vis[a]=1;
for(i=1;i<=n;i++)
if(d[a][i]>0 && !vis[i])R[i]--;
for(i=1;i<=n;i++)
if(vis[i]==0 && R[i]==0)
{
sum+=dfs(i,depth+1);
}
for(i=1;i<=n;i++)
if(d[a][i]>0 && !vis[i])R[i]++;
vis[a]=0;
return sum;
}
int main()
{
int i,m,a,b,ans=0;
scanf("%d%d",&n,&m);
memset(d,0,sizeof(d));
memset(R,0,sizeof(R));
memset(vis,0,sizeof(vis));
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
if(a==b)continue;
d[a][b]=1;
R[b]++;
}
for(i=1;i<=n;i++)
if(R[i]==0)
ans+=dfs(i,1);
printf("%d",ans);
return 0;
}
```
by Patchouli_Nine @ 2016-12-25 20:28:43