#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int marc[MAXN], a[MAXN], b[MAXN];
double val[MAXN];
vector<pair<int, int>> adj[MAXN];
vector<int> comp;
double x; bool ok;
void dfs(int v){
marc[v] = 1;
comp.push_back(v);
for(auto [u, w] : adj[v]){
if(!marc[u]){
a[u] = -a[v], b[u] = w - b[v];
dfs(u);
} else{
if(a[u] + a[v] != 0){
x = ((double) (w - b[u] - b[v])) / ((double) (a[u] + a[v]));
ok = false;
}
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for(int i=1; i<=m; i++){
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
for(int i=1; i<=n; i++){
if(!marc[i]){
comp.clear(); ok = true;
a[i] = 1, b[i] = 0;
dfs(i);
if(ok){
vector<int> median;
for(auto j : comp){
if(a[j] > 0) median.push_back(b[j]);
if(a[j] < 0) median.push_back(-b[j]);
}
sort(median.begin(), median.end());
x = (double) median[(int) median.size() / 2];
}
for(auto j : comp) val[j] = a[j] * x + b[j];
}
}
for(int i=1; i<=n; i++){
for(auto [j, w] : adj[i]){
if(val[i] + val[j] - w > 1e-6){
cout << "NO\n";
return 0;
}
}
}
cout << "YES\n";
cout << fixed << setprecision(6);
for(int i=1; i<=n; i++) cout << val[i] << " ";
cout << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |