L3-1 那就别担心了 天梯赛题解

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

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

输入格式：

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

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

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

输出格式：

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

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

输入样例 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

问题描述

给定一个逻辑推理图，其中：

• 节点代表命题（编号1到N）
• 边代表推理关系（从S1可以推出S2）

要求：

1. 计算从命题A到命题B的不同推理路径数量
2. 判断这个推理是否是"逻辑自洽"的（即从A出发的所有路径都能到达B）

初始解决方案

我最初的想法是使用深度优先搜索（DFS）来遍历所有可能的路径：

#include<bits/stdc++.h>
using namespace std;
//#define int double
//stack<char>s2;
//stack<int>s1;
//char g[1005];
//int s[1005];
//map<string,int>m;
//struct node{
//	string name;
//	string hao;
//	int s1;
//	string time;
//}C[50005];
//node D[2000];
//int flag=1;
//bool cmp(node a,node b)
//{
//	return a.time<b.time;
//}
int a,b;

struct node{
	int l,r;
}C[5005];
int n,m;
int ji[5005]; 
int D[5005][5005];
int num=0;
int allflag=0;
void dfs(int x)
{
	if(x==m)
	{
		num++;
		return ;
	}
	if(ji[x]==1)return ;
	ji[x]=1;
	int flagg=1;
	
	for(int i=1;i<=a;i++)
	{
		if(D[x][i]==1)
		{
			flagg=0;
			dfs(i);
		 } 
	}
	if(flagg==1&&x!=m)
		{
			allflag=1;
		}
//		return;
	ji[x]=0; 
}
signed main()
{

	cin>>a;

	cin>>b;
	for(int i=1;i<=b;i++)
	{
		int c,d;
		cin>>c>>d;
		D[c][d]=1;
//		C[n].l++;
//		C[m].r++;
	}
	
	cin>>n>>m;
	dfs(n);
	cout<<num<<" ";
	if(allflag==1)cout<<"No";
	else cout<<"Yes";
	return 0;
 } 

问题分析

经过分析，我发现DFS的时间复杂度在最坏情况下可能达到O(N!)，这对于N=500来说显然不可行。需要更高效的算法来解决这个问题。

优化方案

1. 记忆化搜索

通过记录每个节点到终点的路径数量，避免重复计算：

int dfs_memo(int u) {
    if(u == target) return 1;
    if(dp[u] != -1) return dp[u];
    
    dp[u] = 0;
    for(int v : graph[u]) {
        dp[u] += dfs_memo(v);
    }
    return dp[u];
}

2. 拓扑排序+动态规划

更高效的解决方案是使用拓扑排序结合动态规划：

1. 对图进行拓扑排序
2. 按照逆拓扑序计算每个节点到终点的路径数

void topological_sort() {
    // 计算入度
    vector<int> in_degree(n+1, 0);
    for(int u = 1; u <= n; ++u) {
        for(int v : graph[u]) {
            in_degree[v]++;
        }
    }
    
    // 拓扑排序
    queue<int> q;
    for(int u = 1; u <= n; ++u) {
        if(in_degree[u] == 0) q.push(u);
    }
    
    vector<int> topo_order;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        for(int v : graph[u]) {
            if(--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
}

3. 逻辑自洽性检查

在计算路径数的同时，检查是否存在无法到达终点的路径：

bool is_consistent = true;
for(int u : topo_order) {
    if(u != target && dp[u] == 0 && has_path_to_start[u]) {
        is_consistent = false;
        break;
    }
}

最终解决方案

结合上述优化，最终的解决方案如下：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 505;
vector<int> graph[MAXN];
int dp[MAXN];
int visited[MAXN];
int has_path[MAXN];
int n, m;

void dfs(int u, int target) {
    if (u == target) {
        dp[u] = 1;
        has_path[u] = 1;
        return;
    }
    if (visited[u]) return;
    visited[u] = 1;
    dp[u] = 0;
    has_path[u] = 0;
    for (int v : graph[u]) {
        dfs(v, target);
        dp[u] += dp[v];
        if (dp[v] > 0) {
            has_path[u] = 1;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    int A, B;
    cin >> A >> B;
    memset(visited, 0, sizeof(visited));
    memset(dp, 0, sizeof(dp));
    memset(has_path, 0, sizeof(has_path));
    dfs(A, B);
    bool is_consistent = true;
    for (int i = 1; i <= n; ++i) {
        if (visited[i] && !has_path[i] && i != B) {
            is_consistent = false;
            break;
        }
    }
    cout << dp[A] << " " << (is_consistent ? "Yes" : "No") << endl;
    return 0;
}