SDUT DAG优化
题目描述
大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。
输入
输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数
之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * /
保证AB的值不同,例如:A=B+C。
输出
通过构造DAG图,进行代码优化,只需要保留AB,删除无用变量,删除变量时,尽量保留最早出现的变量。
Input
3
A=B+C
B=B+B
A=C+C
Output
B=B+B
A=C+C
代码
#include <bits/stdc++.h>
using namespace std;
int falg[11111], n;
char ans[11111][11111];
struct node
{
int l, r;
char op;
vector<char> fu;
} tr[1000];
int cnt = 0;
void dfs(int x)
{
if (tr[x].l && tr[x].r)
{
falg[x] = 1;
dfs(tr[x].l);
dfs(tr[x].r);
}
}
int make(char x)
{
for (int i = 1; i <= cnt; i++)
if (find(tr[i].fu.begin(), tr[i].fu.end(), x) != tr[i].fu.end() || tr[i].op == x)
return i;
tr[++cnt].op = x;
return cnt;
}
void add(char root, int l, int r, char op)
{
for (int i = 1; i <= cnt; i++)
if (tr[i].l == l && tr[i].r == r && tr[i].op == op)
{
tr[i].fu.push_back(root);
return;
}
tr[++cnt] = {l, r, op};
tr[cnt].fu.push_back(root);
}
void solve(int id, int pos, int ci)
{
if (tr[id].fu.size() == 0)
{
ans[pos][ci] = tr[id].op;
return;
}
for (int i = 0; i < tr[id].fu.size(); i++)
if (tr[id].fu[i] == 'A' || tr[id].fu[i] == 'B')
{
ans[pos][ci] = tr[id].fu[i];
return;
}
ans[pos][ci] = tr[id].fu[0];
}
signed main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
int l = make(s[2]), r = make(s[4]);
char root = s[0], op = s[3];
add(root, l, r, op);
}
for (int i = 1; i <= cnt; i++)
if (tr[i].l && tr[i].r)
{
ans[i][1] = '=', ans[i][3] = tr[i].op, ans[i][5] = '\0';
solve(i, i, 0);
solve(tr[i].l, i, 2);
solve(tr[i].r, i, 4);
}
for (int i = cnt; i >= 1; i--)
if (ans[i][0] == 'A')
{
dfs(i);
break;
}
for (int i = cnt; i >= 1; i--)
if (ans[i][0] == 'B')
{
dfs(i);
break;
}
for (int i = 1; i <= cnt; i++)
if (falg[i])
cout << ans[i] << endl;
}
标签:DAG,int,tr,dfs,char,SDUT,ans,优化
From: https://www.cnblogs.com/zzh1206/p/17056304.html