返回信息流我用的暴力法，先将条件中的推导式扩展，扩展出所有它可以推导的式子。然后把要推断的式子带入一一验证。
题目描述
数理逻辑是计算机科学中很重要的一环，而公式的自动推导就是这门科学的研究方向之一。虽然目前复杂的公式推导还难以做到，但一个简单的推导机器还是可以很容易实现的
一个“蕴含式”可以表示为 A --> B ，意为A可以推出B，其中A和B均为非空的条件的集合（在本题中每一个条件用单独的一个小写字母表示）。比如 abc --> de 表示如果条件a、b、c均成立则可以推出d、e都成立。
现已知有N个 推导规则。最后给出一条新的推导规则，在已知的情况，求最后一条规则是否成立
HINT对公式的读入建议使用scanf(“%s%*s%s”,a,b)
公式的推导基于Armstrong 公理，即满足：
自反律：若属性集Y 包含于属性集X，属性集X 包含于U，则X–>Y 在R 上成立。
增广律：若X –> Y 在R 上成立，且属性集Z 包含于属性集U，则XZ–>YZ 在R 上成立。
传递律：若X –> Y 和 Y –> Z在R 上成立，则X –> Z 在R 上成立。
代码：
#include<stdio.h>
#include<string.h>
char cause[2000][26],result[2000][26];
int aaa(char pcause1[],char presult1,int n)
{
int flag=0,i;
for(i=0;i<n;i++)
{
if(strchr(result[i],presult1)!=NULL&&strstr(pcause1,cause[i])!=NULL)
{
return 1;
}
}
return 0;
}
int main()
{
int n,i,f,j,k,q,sum;
char tuidao[4],pcause[26],presult[26];
char tong[26],pxcause[26],pxresult[26];
int flag=0;
int count1=0;
int count2=0;
while(scanf("%d",&n)!=EOF)
{
getchar();
for(i=0;i<n;i++)
{
scanf("%s%s%s",cause[i],tuidao,result[i]);
//getchar();
}
scanf("%s%s%s",pcause,tuidao,presult);
int clen=strlen(pcause);
int rlen=strlen(presult);
if(strcmp(pcause,presult)==0)
{
printf("YES\n");
continue;
}
else if(strstr(pcause,presult)!=NULL)
{
printf("YES\n");
continue;
}
else if(strstr(presult,pcause)!=NULL)
{
printf("NO\n");
continue;
}
else
{
sum=0;
for(i=0;i<clen;i++)
{
for(j=0;j<rlen;j++)
{
if(pcause[i]==presult[j])
{
tong[sum]=pcause[i];
sum++;
}
}
}
if(sum)
{
for(i=0;i<clen;i++)
{
flag=1;
for(j=0;j<sum;j++)
{
if(pcause[i]==tong[j])
{
flag=0;
}
}
if(flag)
{
pxcause[count1++]=pcause[i];
}
}
pxcause[count1]='\0';
for(i=0;i<clen;i++)
{
flag=1;
for(j=0;j<sum;j++)
{
if(presult[i]==tong[j])
{
flag=0;
}
}
if(flag)
{
pxresult[count2++]=presult[i];
}
}
pxresult[count2]='\0';
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
continue;
else
{
if(strstr(result[i],cause[j])!=NULL)
{
strcpy(cause[n],cause[i]);
strcpy(result[n],result[j]);
n++;
}
}
}
}
}
if(sum==0)
{
f=1;
for(i=0;i<strlen(presult);i++)
{
f=f&&aaa(pcause,presult[i],n);
if(f==0)
{
printf("NO\n");
continue;
}
}
}
else
{
f=1;
for(i=0;i<count2;i++)
{
f=f&&aaa(pxcause,pxresult[i],n);
if(f==0)
{
printf("NO\n");
continue;
}
}
}
if(f==1)
printf("YES\n");
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92282同步于 2017/3/9
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】oj106 公式推导，总是提交时答案错误，求帮忙改正
gungnir0123
2017/3/9镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
预处理构造成一个图，然后BFS，代码写的比较挫不知道楼主能不能看懂。。
```C
/*
USER_ID: test#lzj_0218
PROBLEM: 106
SUBMISSION_TIME: 2017-03-10 15:53:28
*/
/* 解题思路:
* 首先进行预处理，将输入的n个推导公式构造成一个图，构造方法如下：
* 以 abc --> de 为例，在图中加入以下6条边：
* a --bc--> d b --ac--> d c --ab--> d
* a --bc--> e b --ac--> e c --ab--> e
* 然后根据已知条件，BFS搜索判定能否推导出结论
* 图的存储使用了位运算来节省内存
**/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;
struct EDGE {
int info;
int to;
};
vector<EDGE> edges[26];
int compute_info(const char *str, const int len, const int kill) {
int res = 0;
for (int i = 0; i < len; i++) {
res = res | (1 << (str[i] - 'a'));
}
res = res & ~(1 << kill);
return res;
}
int curr_info;
bool get[26];
int main() {
int n = 0;
while (scanf("%d", &n) == 1) {
for (int i = 0; i < 26; i++) {
edges[i].clear();
}
char from_buff[30] = {0};
char to_buff[30] = {0};
for (int k = 0; k < n; k++) {
scanf("%s%*s%s", from_buff, to_buff);
int len_from = strlen(from_buff);
int len_to = strlen(to_buff);
for (int i = 0; i < len_from; i++) {
const int kill = from_buff[i] - 'a';
const int edge_info = compute_info(from_buff, len_from, kill);
for (int j = 0; j < len_to; j++) {
const int edge_to = to_buff[j] - 'a';
EDGE tmp_edge;
tmp_edge.info = edge_info;
tmp_edge.to = edge_to;
edges[kill].push_back(tmp_edge);
}
}
}
scanf("%s%*s%s", from_buff, to_buff);
int len_from = strlen(from_buff);
int len_to = strlen(to_buff);
memset(get, 0, sizeof(get));
curr_info = 0;
queue<int> bfs_queue;
for (int i = 0; i < len_from; i++) {
int tmp = from_buff[i] - 'a';
get[tmp] = true;
curr_info = curr_info | (1 << tmp);
bfs_queue.push(tmp);
}
while (!bfs_queue.empty()) {
int edge_from = bfs_queue.front();
bfs_queue.pop();
for (size_t i = 0; i < edges[edge_from].size(); i++) {
if (get[edges[edge_from][i].to]) {
continue;
}
if ((edges[edge_from][i].info & curr_info) == edges[edge_from][i].info) {
get[edges[edge_from][i].to] = true;
curr_info = curr_info | (1 << edges[edge_from][i].to);
bfs_queue.push(edges[edge_from][i].to);
}
}
}
bool res = true;
for (int i = 0; res && i < len_to; i++) {
if (!get[to_buff[i] - 'a']) {
res = false;
}
}
printf("%s\n", res ? "YES" : "NO");
}
return 0;
}
```
【 在 gungnir0123 的大作中提到: 】
: 我用的暴力法，先将条件中的推导式扩展，扩展出所有它可以推导的式子。然后把要推断的式子带入一一验证。
: 题目描述
: 数理逻辑是计算机科学中很重要的一环，而公式的自动推导就是这门科学的研究方向之一。虽然目前复杂的公式推导还难以做到，但一个简单的推导机器还是可以很容易实现的
: ...................
多谢，昨天有点事，就一直没看北邮人论坛，我也是把输入的公式预处理得到所有可以推出的公式，然后看里面有没有要推出的公式在里面，但是答案报错，是不是我预处理有问题，还是我对题目的理解有问题。
【 在 lzj0218 的大作中提到: 】
: [md]
: 预处理构造成一个图，然后BFS，代码写的比较挫不知道楼主能不能看懂。。
:
: ...................
太感谢了，我学习学习，我觉得自己思路是对的，估计实现中有问题或者本身对题目的理解有问题