麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

Round C APAC Test 2017 Problem C. Evaluation（拓?fù)渑判颍?/h1>
2019-11-14 09:46:15
字體：大 中 小
來(lái)源：轉(zhuǎn)載
供稿：網(wǎng)友

題目鏈接

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

題意

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

思路

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

細(xì)節(jié)

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

代碼

#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;}

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表

主站蜘蛛池模板： 国产精品一区视频 | 久久国产精品久久久久久电车 | 欧美黄 片免费观看 | 草莓福利视频在线观看 | 在线播放免费视频 | av视在线 | 成人区一区二区 | 黄色特级视频 | 久久精品亚洲一区二区三区观看模式 | 国产成人精品视频在线 | 成人免费观看49www在线观看 | omofun 动漫在线观看 | 欧美黄色一级生活片 | 特黄一级小说 | 欧美高清在线精品一区二区不卡 | 日本在线免费观看视频 | 欧美一级做a | 欧美精品一区二区三区在线 | 欧美日韩国产成人在线观看 | 精国品产一区二区三区有限公司 | 成码无人av片在线观看网站 | 国产精品一区二区在线 | 亚州综合 | 国产精品亚洲综合 | 久久精品性视频 | 91快色视频| qyl在线视频精品免费观看 | 美国一级免费视频 | 国产精品视频导航 | 一区二区久久精品66国产精品 | 欧美国产第一页 | 亚洲国产一区二区三区 | 日本在线视频一区二区三区 | 日本成人午夜 | 亚洲性爰 | 欧美精品一区二区久久 | 欧美精品一区二区久久 | 免费毛片在线 | 午夜视 | 草久视频在线观看 | 69av导航 |