7-143 那就别担心了

发布于：2022-10-13 ⋅ 阅读:(214) ⋅ 点赞:(0)

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有 3 条不同的推理路径。

输入格式：

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

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

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

输出格式：

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

题目保证输出数据不超过 10^9。

输入样例 1：

输出样例 1：

3 Yes

输入样例 2：

输出样例 2：

3 No

考察 : 单源路径优化

注意 : 无优化暴力搜索会超时

思路 : 见代码

C/C++

#include<bits/stdc++.h>
using namespace std;
vector<int> road[501];
map<int,int> flag,appear1,appear2; // 该点有几条路可达终点 , 动态规划 , 该点判断过没
int result=1,head,tail;
void find(int now,int last);
int main()
{
    int N,M,a,b;
    cin >> N >> M;
    for(int z=0;z<M;z++) {
        cin >> a >> b;
        road[a].push_back(b);
    }
    cin >> head >> tail;
    find(head,0);
    cout << flag[head] << " " << (result ? "Yes" : "No") << endl;
    return 0;
}
void find(int now,int last){
    if(now==tail) flag[last] += 1;
    else if(road[now].empty()) result = 0;
    else if(!appear1[now])
    {
        appear1[now] = true;
        for(int& x:road[now])
        {
            if(appear2[x]) flag[now] += flag[x];
            else find(x,now);
        }
        appear1[now] = false;
        appear2[now] = true;
        flag[last] += flag[now];
    }
}