python()

这是一个记忆化dp优化的基于递归的dfs

这道题没有用到dp 但是加上也不是坏习惯

如果改成每条边最多走k次 存在状态想同的情况 那记忆化就有用了

import sys
#sys是python的内置系统库
sys.setrecursionlimit(1000000)
#调整递归深度限制 防止无限递归栈溢出 通常是1000层左右 超出这个限制会报错
#但是最坑的一点是 其实他没啥用。该崩还是得崩。 因为栈空间有限
#它的作用就是会让程序直接崩溃 而不是报错。
"""递归和栈有什么关系？
递归是用系统的栈来实现的 每次函数调用时 系统会在调用栈上压入一个栈帧
包含函数参数 局部变量 返回地址

为什么一定是栈？ 不是列表？
因为函数调用遵循后进先出的天然规律 就是最后被调用的函数最先返回 
比如:
def a():
    b()
def b():
    c()
def c():
    return
a()
执行顺序是a到b 返回顺序是a b c 返回顺序是c b a 最后被调用的函数最先返回 
这是栈的特性 并且栈保证了操作总是同一端 不会出错 列表可能存在移除中间的情况
其次 计算机的cpu有专门的栈指针寄存器 call指令把返回地址压栈 跳转到新函数
ret把栈顶弹出地址跳转回去 是硬件级别的优化

什么是栈帧？
存储当前的函数参数 局部变量 返回地址
说简单一些就是用于存储目前信息便于返回的一个存档

为什么需要栈帧？
因为计算机只能执行一个函数 当新函数开始时 必须保存现场 执行新函数 再返回原位

什么是调用帧？
调用帧就是栈帧 和父亲和爸爸的概念一样

为什么会栈溢出？
因为存档太多存不下了 所以才会设置递归深度 就是要调整可以存储的存档上限
因为平常递归深度就是1000左右 所以一旦要超过这个范围必须要调整递归上限

"""
 #虽然外层函数和内层函数都有u这个变量 但是外层的u是属于for循环的 内层的u属于dfs函数 所以不会冲突 他们的作用域不同
def main():
    n, m = map(int, sys.stdin.readline().split())
    #多开一个位置涉及到数组下标从1开始的编程习惯
    g = [[] for _ in range(n + 1)]
    #这里的i是0-based的设计十分重要 因为二进制中第0位存储的是第一个通道
    #需要往右移动0个单位 因此第一个通道的索引必须是0 
    #如果是1，m+1 会导致第一个通道往右移动一位导致判断的是第二个通道！
    for i in range(m):
        u, v = map(int, sys.stdin.readline().split())
        #以通道的开头为索引 存储列表中 存储的内容是通道的结尾和序号
        g[u].append((v, i))
    
    # 导入记忆化板块
    # 虽然这道题由于每条边只能走一次，不会出现重复状态
    # 但加上记忆化是良好的编程习惯，对于更复杂的问题很有用(ds说的 这句话不是我说的)
    from functools import lru_cache
    
    @lru_cache(None)
    #used_mask 是通道的使用情况 有多少个通道就有多少位
    #u是通道的开头
    def dfs(u, used_mask):
        #直接结束的话算一种 并且这个count还承担了累加器的基础值
        count = 1 

        """dfs核心程序:
        
        v是通道的结尾 eid是通道的序号 u是通道的开头 这里的意思就是 
        由于前面保存的是通道的开头中含有 通道的终点 所以是在这个开头中寻找终点
        并且在找到后 以这个终点v递归作为上面的起点u 继续寻找 
        如果一个分支没有找到 就返回起点 再找没有用过的通道 如果实在找不到 就返回上一个
        起点 比如 1 可以去2 3 ,然后2可以去4 ,当1到2后 终点2变为起点2 搜索到终点4 
        4为起点后找不到 返回起点2 再找 找不到返回上一个起点1 找到分支3 循环彻底结束 输出
        累加的count """ 
        
        for v, eid in g[u]:
            #因为0是false 那么加了not之后就是true
            #就是只有当最后一位是0 才可以往下进行 
            if not (used_mask >> eid) & 1: 
                #下面就是一个dfs 开始搜索以通道结尾开头的通道
                #如果已经用过了 就继找 
                count += dfs(v, used_mask | (1 << eid))
              #这里一定要用vid的二进制掩码来计算 因为如果是2的话 我们实际上是想标记第二个位置的 
      #举个简单的例子就是从0000变成0100 但是如果不是掩码的话 直接used_mask | 2  2的二进制是0010 所以就会变成0010 而不是0020 
      #意思就是要把2路径转换成二进制表达的2路径所在地 而不是数字二 因为2转换为二进制所表达的数字与表达为路径二所表达的数字不一样 
      #二进制的路径二被标记的时候应该是0100 是一个4 但是把二转换为二进制却不是平移的话 最后的记结果其实是路径1被标记了
        
        return count
    #主程序位置 
    #为什么开头是1,0？
    #因为轨道是1-based存储进去的
    ans = dfs(1, 0)  
    print(ans)

if __name__ == "__main__":
    main()


#无注释版：
import sys
sys.setrecursionlimit(1000000)

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    
    for i in range(m):
        u, v = map(int, input().split())
        g[u].append((v, i))
    
    from functools import lru_cache
    
    @lru_cache(None)
    def dfs(u, used_mask):
        count = 1
        for v, eid in g[u]:
            if not (used_mask >> eid) & 1:
                count += dfs(v, used_mask | (1 << eid))
        return count
    
    ans = dfs(1, 0)
    print(ans)

if __name__ == "__main__":
    main()

题解

Writer: Yue_chen

题意

$n$ 个点，$m$ 条有向边，从点 $1$ 出发，每次走一条没走过的边，可以随时结束，问有多少种走法。

分析

题目的 $n$ 虽然大的惊人，但是 $m$ 却小的可怜。

无需考虑优化，我们将之前走过的边记录下来，每次暴力枚举 $m$ 次，找一条没走过的边去走，用dfs去考虑第 $i$ 天走哪条边，vis数组去记录那些边是前 $i$ 天走过的，方法比较经典。

代码

using namespace std;

using i64 = long long;

void solve() {
	int n, m; cin >> n >> m;

    //存边，array<int,2> = pair<int,int> = 两个int
    vector<array<int,2>> e(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> e[i][0] >> e[i][1];
    }
    
    vector<int> vis(m + 1);
  //局部内函数写法，看不懂的在函数外面正常写就行
    function<int(int)> dfs = [&](int u) {
        int ans = 1;
        for (int i = 1; i <= m; i++) {
            if (e[i][0] == u and !vis[i]) {
                vis[i] = 1;
                ans += dfs(e[i][1]);
                vis[i] = 0;
            }
        } return ans;
    };
    cout << dfs(1) << "\n";
}

signed main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}