DAG优化-详解

DAG优化

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。

Input

输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数

之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 + - * /

例如：A=B+C

Output

通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。

PS:保证AB的值不同

Sample Input

3
A=B+C
B=B+B
A=C+C

Sample Output

B=B+B
A=C+C
我在网上看了好多代码AC这个题都是接近90多行，而且没有注释，看起来非常难理解，搜了很久才发现一个不同其他写法的博主的博客，而且只有四十多行，但是也没有注释，我花了一个多小时理解通，然后给大家加上注释

#include <bits/stdc++.h>
//主要是思想是，由于题目要求只保留和A,B相关的，所以与A,B相关的式子也需要保存，
//比如A=C+D,则C=***和D=***的式子也需要保存，
using namespace std;
int print[100];//这个数组，里面只保存0或者1,是1则说明这个式子是优化后需要输出的
char formula[100][20];//这个是一个字符串数组类似于String formula[];
int revelant[300];//这个数组是用来将A,B或者与A,B相关的字母的ACCII码的下标，存为1，比如revelant['A']=1,等价于revelant[65]=1;
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%s",formula[i]);//将需要输入的表达式先全部存到forMula中
    memset(revelant,0,sizeof(revelant));
    memset(print,0,sizeof(print));
    revelant['A']=revelant['B']=1;//先将revelant[65]=1,revelant[66]=1,
    for(int i=n; i>=1; i--)//这个循环是用来保存只和A,B相关的式子，相当于删除无用表达式
    {//其中与A,B相关的等式，比如formula[i]这个表达式与A,B相关，这print[i]=1

        if(revelant[(int)formula[i][0]]==1)
        {
            print[i]=1;
            revelant[(int)formula[i][0]]=0;//这个主要是去除无用赋值,比如A=B+C,A=D+F,后面的赋值会覆盖前面的值
            revelant[(int)formula[i][2]]=1;
            revelant[(int)formula[i][4]]=1;
        }
    }
    for(int i=1; i<=n; i++)
    {

        if(print[i]==1)
        {

            if(formula[i][0]=='A'||formula[i][0]=='B')//如果是A/B=D+C，等号左边是A,B,这不执行任何操作，因为A=***,是必须要输出的优化后代码一项
                continue;//
            for(int j=1; j<=i-1; j++)
            {

                if(formula[i][2]==formula[j][2]&&formula[i][3]==formula[j][3]&&formula[i][4]==formula[j][4])//比如A=C+D,C=G+F需要找出,i前面*=G+F这样的式子，删除相同的赋值，且优先保留最早的。直接break
                {
                    print[j]=1;//删除多余的一个，剩下的一个所对应的下标，要赋为1，表示需要输出的表达式
                    print[i]=0;
                    for(int k=i+1; k<=n; k++)//这个就是比如这是第i项C=G+F,第j项为*=G+F
                    {//因为第i项已经删除，所以后面应用到C的需要换成*，比如第i+3项为D=C+B,则需要换成D=*+B
                        if(formula[k][0]==formula[i][0])break;
                        if(formula[k][2]==formula[i][0]) formula[k][2]=formula[j][0];
                        if(formula[k][4]==formula[i][0]) formula[k][4]=formula[j][0];

                    }
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {//输出标记为1的式子

        if(print[i]==1)
            printf("%s\n",formula[i]);
    }

}