记忆化搜索（貌似，不太清楚是不是，自己摸索题的时候猜了一个） L3-025 那就别担心了 (30 分).md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

题目

<https://pintia.cn/problem-
sets/994805046380707840/problems/1336215880692482060>
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。
![在这里插入图片描述](https://img-
blog.csdnimg.cn/img_convert/c391ed5f2575c951739264f1eb9226e7.png#pic_center)
博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有
3 条不同的推理路径。

输入格式：
输入首先在一行中给出两个正整数 N（1<N≤500）和 M，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1 S2，表示可以从 S1 推出
S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。

最后一行给出待检验的两个命题的编号 A B。

输出格式：
在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。

题目保证输出数据不超过 1e9。

输入样例 1：
7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1
输出样例 1：
3 Yes
输入样例 2：
7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1
输出样例 2：
3 No

代码

一开始暴力dfs最后一个样例过不了，不是开了一个vis数组记录。刚开始瞎记录，把找到终点的路径标记为true，但是会发生路径数与最终答案不同的错误。后来发现vis数组应该开int类型。然后继续摸索。
ac后总结了一下，vis数组记录的是当前节点通往终点的路径条数。
代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <set>

const int N = 505, M = 250005;

int head[N],dout[N],vis[N];
int idx;
int n,m,u,v,to,zero;
int ans;

struct Edge{
   int to,nxt;
}edge[M];

int dfs(int x){
   if(vis[x]) {
      ans += vis[x];
      return vis[x];
   }
   if(!dout[x]){
      zero += 1;
      dout[x] = -1;
      return 0;
   }
   for(int i=head[x]; i!=-1; i= edge[i].nxt){
      to = edge[i].to;
      vis[x] += dfs(to);
   }
   return vis[x];
}

int main()
{
   idx = -1;
   memset(head,-1,sizeof(head));
   scanf("%d%d",&n,&m);
   for(int i=0; i<m; i++){
      scanf("%d%d",&u,&v);
      edge[++idx] = {v,head[u]}; head[u] = idx;
      dout[u] += 1;
   }
   scanf("%d%d",&u,&v);
   vis[v] = 1;
   dfs(u);
   printf("%d %s",ans,(!zero) ? "Yes" : "No");
   return 0;
}

StarsWhisper

说明 - 2022-05-05

题目

代码