Round C APAC Test 2017 Problem C. Evaluation（拓撲排序）

2019-11-14 09:46:15

字體：大中小

來源：轉載

供稿：網友

題目鏈接

https://code.google.com/codejam/contest/6274486/dashboard#s=p2

題意

給定若干個等式，這些等式的順序可以交換。等式左邊的值依賴于右邊的值，要求判斷等式是否合法。

思路

我們要解決的問題就是判斷這些變量是否存在相互依賴的關系。假如a = f(b, c)。那么a依賴于b和c，我們就從b和c分別連一條邊到a。最后要判斷的問題就是這個圖是否存在環。

細節

注意假如a = f(b, c)，即a依賴于b和c，那么b和c必須要在等式左邊出現過（即b，c一定能夠被算出來）

代碼

#include <bits/stdc++.h>using namespace std;inline int in() {int x; scanf("%d", &x); return x;}#define PR(x) {cout << #x << ' ' << x << endl;}const int maxn = 100000 + 5;const int maxm = 2005;vector<int> G[maxn];int In[maxn], n, tot, musthas[maxn];vector<int> has;char s[maxm];map<string, int> mmp;void init() { for (int i = 0; i < maxn; i++) G[i].clear(); memset(In, 0, sizeof(In)); memset(musthas, 0, sizeof(musthas)); mmp.clear(); has.clear(); n = 0; tot = 0;}void pre(string s) { bool flag = false; int k = s.find("="); //create to string sv = s.substr(0, k); if (mmp.find(sv) == mmp.end()) mmp[sv] = ++n; int v = mmp[sv]; has.push_back(v); //create from string ss = ""; vector<int> tmp; for (int i = k + 1; i < s.length(); i++) { if (s[i] == '(') {flag = true; continue;} if (s[i] == ')') break; if (flag) { if (s[i] == ',' || i == s.length() - 2) { if (i == s.length() - 2 && s[i] != ',') ss += s[i]; if (mmp.find(ss) == mmp.end()) mmp[ss] = ++n; int u = mmp[ss]; musthas[u] = 1; G[u].push_back(v); In[v]++; ss = ""; } else { ss += s[i]; } } }}bool nocircle() { queue<int> q; int cnt = 0; for (int i = 1; i <= n; i++) if (!In[i]) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (auto v : G[u]) { In[v]--; if (!In[v]) q.push(v); } } return cnt == n;}int main() { int T = in(); int kase = 0; while (T--) { init(); int ca = in(); while (ca--) { string s; cin >> s; pre(s); } cout << "Case #" << ++kase << ": "; bool fl = false; for (auto x : has) { if (musthas[x]) musthas[x] = 0; } for (int i = 1; i <= n; i++) { if (musthas[i]) { cout << "BAD" << endl; fl = true; break; } } if (!fl) { if (nocircle()) cout << "GOOD" << endl; else cout << "BAD" << endl; } } return 0;}

上一篇：Dijkstra算法的C語言程序

下一篇：POJ 3661 Running 動態規劃刷表法