| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726719 |
2023-04-19T09:28:01 Z |
YENGOYAN |
Graph (BOI20_graph) |
C++17 |
|
0 ms |
0 KB |
/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e9;
vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };
void solve() {
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> gp(n);
for(int i = 0; i < m; ++i){
int u, v, w; cin >> u >> v >> w; w *= 2;
gp[--u].push_back({--v, w});
gp[v].push_back({u, w});
}
vector<int> ans(n, inf), val(n), comp;
vector<bool> vis;
int sm = 0;
function<void(int)> dfs = [&](int u){
vis[u] = 1;
if(sm != inf) {
sm += abs(val[u]);
}
comp.push_back(u);
for(pair<int, int> &v : gp[u]) {
for(int i = 0; i < n; ++i) {
if(gp[i].size() == 0 && i != root) {
to_col.insert(i);
}
}
if(!vis[v.first]) {
val[v.first] = v.second - val[u];
dfs(v.first);
}
else if(val[u] + val[v.first] != v.second) {
sm = inf;
}
}
};
vector<int> res(n, 1e9);
for(int a = -20; a <= 20; ++a){
vis = vector<bool> (n);
val = vector<int> (n);
for(int i = 0; i < n; ++i) {
if(vis[i]) {
continue;
}
sm = 0;
val[i] = a;
comp.clear();
dfs(i);
if(sm < ans[i]) {
ans[i] = sm;
for(int &u : comp) {
res[u] = val[u];
}
}
}
}
for(int i = 0; i < n; ++i){
if(res[i] == 1e9){
cout << "NO\n";
return;
}
}
cout << "YES\n";
for(int i = 0; i < n; ++i) {
cout << double(res[i] / 2.0) << " ";
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int t; cin >> t; while(t--)
solve();
}
Compilation message
Graph.cpp: In lambda function:
Graph.cpp:65:38: error: 'root' was not declared in this scope
65 | if(gp[i].size() == 0 && i != root) {
| ^~~~
Graph.cpp:67:11: error: 'to_col' was not declared in this scope
67 | to_col.insert(i);
| ^~~~~~
