求拓扑排序的数量,例题 topcoder srm 654 div2 500
周赛时遇到的一道比较有意思的题目:
Problem Statement |
|||||||||||||
There are N rooms in Maki's new house. The rooms are numbered from 0 to N-1. Some pairs of rooms are connected by bidirectional passages. The passages have the topology of a tree. That is, there are exactly N-1 of them and it is possible to go from any room to any other room by following some sequence of passages. You are given two vector <int>s a and b that describe the passages. For each valid i, there is a passage that connects the rooms a[i] and b[i]. You are also given an int s. The house has exactly one entrance from the outside, and the entrance leads to the room s. Niko is helping Maki move into the new house. Maki has exactly N pieces of furniture. The pieces are numbered from 0 to N-1. Niko will carry them into the house in this order. Each piece of furniture must be placed into a different room. Maki does not care which piece goes where, each of the N! permutations is allowed. However, not all of those N! permutations are actually possible. This is because the furniture is large. As soon as a room contains a piece of furniture, it is impossible to move other pieces through this room. Thus, Niko must place the furniture carefully. Formally, she can place a new piece of furniture into the room x if and only if all rooms on the (unique) path between s and x, including s and x, are still empty. Niko is smart and she will always place the furniture in such a way that she never gets stuck. Thus, at the end each of Maki's rooms will contain exactly one piece of furniture. Calculate and return the number of ways how the furniture can be arranged in Maki's house at the end. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Limits |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
- | N will be between 1 and 9, inclusive. | ||||||||||||
- | a and b will contain exactly N-1 elements each. | ||||||||||||
- | Each element of a and b will be between 0 and N-1, inclusive. | ||||||||||||
- | The graph described by a and b will be a tree. | ||||||||||||
- | s will be between 0 and N-1, inclusive. | ||||||||||||
Examples |
|||||||||||||
0) | |||||||||||||
|
|||||||||||||
1) | |||||||||||||
|
|||||||||||||
2) | |||||||||||||
|
|||||||||||||
3) | |||||||||||||
|
|||||||||||||
4) | |||||||||||||
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
这道题目也等同于:
假设一个Tree含有N个结点,现在有N个数字 1-N,将这个Tree的N个结点用这N个数字编号,要求父结点一定要大于子结点的编号,一共有多少种编号方式。
这种题目都可以抽象为一个问题:求一个Tree 所有结点的拓扑序列的个数。
求解方式可以用DFS来做:
另int Func() 表示当前Tree 的拓扑排序数量,Func() 可以这么计算:找到当前Tree中所有入度为0的结点,假设有K个这样的结点,对于每个这样的结点,从Tree去掉从该结点出发的边,然后算出去掉边后的Tree 对应的Func()。子Func()的结果的总和,就是 父Func()的结果。
当所有结点都遍历过时,Func() 返回 1
题目中的图表示是用两个vector 表示,所以要先根据这两个vector 构建出单向邻接矩阵 conn[][]
#include<iostream>
#include<vector>
#include<string.h>
using namespace std; class OneEntrance{
public:
int count(vector <int> a, vector <int> b, int s){
N = a.size() + ;
if(N <= ) return N;
memset(conn, , sizeof(conn));
memset(visit, , sizeof(visit));
dfsconn(a, b, s, -); //use a, b to create adjacency matrix(mono-directed)
return dfscount(conn); //based on matrix, get the total amount of topological sequence.
}
private:
bool conn[][];
bool visit[];
int N = ;
void dfsconn(vector<int> &a, vector<int> &b, int cur, int pre){
for(int i = ; i < a.size(); ++i){
if(a[i] == cur && b[i] != pre){
conn[a[i]][b[i]] = true;
dfsconn(a, b, b[i], cur);
}
if(b[i] == cur && a[i] != pre){
conn[b[i]][a[i]] = true;
dfsconn(a, b, a[i], cur);
}
}
}
int dfscount(bool conn[][]){
int i, j, zdgrcnt, cnt = ;
for(i = ; i < N; ++i) cnt += (!visit[i] ? : );
if(cnt == ) return ;
cnt = ;
for(i = ; i < N; ++i){
if(visit[i]) continue;
zdgrcnt = ;
for(j = ; j < N; ++j){
zdgrcnt += (conn[j][i] ? : );
}
if(zdgrcnt == ){ //found one node whose in-order degree is zero
visit[i] = true;
vector<bool> tmp(N, false);
for(j = ; j < N; ++j){
if(conn[i][j]){
tmp[j] = true;
conn[i][j] = false; //remove its out-order edge.
}
}
cnt += dfscount(conn);
for(j = ; j < N; ++j){
if(tmp[j]) conn[i][j] = true;
}
visit[i] = false;
}
}
return cnt;
}
};
dfs 中包含了很多重复计算,毕竟是递归。
动态规划的解法可以参考对 HDU 4661 这一题的解答
传送门: http://www.cnblogs.com/GBRgbr/p/3312866.html
最新文章
- linux原始套接字(4)-构造IP_UDP
- 25条提高iOS app性能的方法和技巧
- github 使用教程初级版
- Unity3D手游开发日记(9) - 互动草的效果
- IOS 杂笔-8(loadView、viewDidLoad、viewWillAppear、viewDidAppear等简介)
- Team Foundation Server 2015(Update 1)集成 SharePoint Server 2013
- CSV to XLSX (专用)
- Java字符串转换
- Jersey框架一:Jersey RESTful WebService框架简介
- EF异常:WebForm、Console、Winform层不引入EF报错
- Java Set接口
- 数据结构(启发式合并):HNOI 2009 梦幻布丁
- mysql 密码过期问题 password_expired
- awk中{print $1}什么意思
- nvarchar 和varchar区别
- JavaScript面向对象(OOP)
- 异常值处理outlier
- 动态规划——Palindrome Partitioning II
- mssql 创建存储过程简单实例
- python全栈开发day57- pymysql、视图、触发器、函数
热门文章
- SignalR实现服务器与客户端的实时通信
- (一)MVC5干货篇,目录和路由
- JAVA的安装与软件使用
- 最近碰到了一个病毒木马:virus.win32.ramnit.B
- WHY数学图形可视化工具(开源)
- liunx 套接字编程(Linux_C++)
- A CIRCULAR PROGRESSBAR STYLE USING AN ATTACHED VIEWMODEL
- SqlServer查看各个表所占空间大小的sql
- HTTP2 学习
- 告诉你吧,一套皮肤在winform与wpf开发模式下实现的界面效果同样精彩,winform界面和wpf界面。