QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698252 | #8760. 不等式 | xingliu# | WA | 0ms | 3880kb | C++20 | 2.4kb | 2024-11-01 18:23:08 | 2024-11-01 18:23:15 |
Judging History
answer
/**
* author: xing huan liu kong
* created: 2024-11-01 17:09:44
*
* 即使这个图论(world)大的无边无际
* 我也会深度优先搜索(dfs)找到你..
**/
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define point(x) fixed<<setprecision(x)
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef array<int, 3> arr;
void solve()
{
int n, m; cin >> n >> m;
vector<vector<int>> e(n);
vector<int> in(n);
for (int i = 0; i < m; i++) {
int x, y, z; cin >> x >> y >> z;
x--, y--, z--;
e[x].push_back(y);
e[x].push_back(z);
in[y]++;
in[z]++;
}
queue<int> q;
vector<int> ans;
for (int i = 0; i < n; i ++ ){
if (!in[i]){
q.push(i); // 先将 入度 为 0 的节点放入
}
}
while (!q.empty()){
int t = q.front();
q.pop();
ans.push_back(t);
for (int i = 0; i < e[t].size(); i ++ ){
int j = e[t][i];
in[j] -- ; // 入度 --
if (!in[j]) { // 入度为 0 放入队列
q.push(j);
}
}
}
if (ans.size() != n) {
cout << -1 << endl;
} else {
int st = -1;
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
st = i;
break;
}
}
vector<int> cnt(n);
auto dfs = [&](auto &&self, int now) -> int {
if (cnt[now]) return cnt[now];
set<int> se;
for (auto &v : e[now]) {
if (se.count(v)) continue;
se.insert(v);
cnt[now] += self(self, v);
}
if (cnt[now] == 0) return cnt[now] = 1;
return cnt[now];
};
dfs(dfs, st);
int res = 0;
for (int i = 0; i < n; i++) {
if (cnt[i] == 0) {
for (auto &v : e[i]) {
cnt[i] += cnt[v];
}
}
res += cnt[i];
// cerr << cnt[i] << " ";
}
cout << (res <= 1e9 ? res : -1) << endl;
}
}
signed main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
while(t -- ){
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3880kb
input:
3 1 1 2 2
output:
2
result:
wrong answer 1st numbers differ - expected: '4', found: '2'