This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define int long long
vector <vector <pair <int,int>>> g;
vector <int> used;
vector <int> comp;
void dfs(int v) {
used[v] = 1;
for(auto [i, j] : g[v]) {
if(used[i] == LLONG_MAX) dfs(i);
}
}
void get_comps() {
for(int i = 0; i < used.size(); i ++) {
if(used[i] == LLONG_MAX) {
dfs(i);
comp.push_back(i);
}
}
}
int check(int v) {
int f = 1;
for(auto [i, j] : g[v]) {
if(used[i] == LLONG_MAX) {
used[i] = j - used[v];
f = min(f, check(i));
}else {
if(used[i] + used[v] != j) f = 0;
}
}
return f;
}
vector <pair <int,int>> rec(int v) {
int mn = LLONG_MAX;
vector <pair <int,int>> ans;
for(int val = -100; val <= 100; val += 1) {
for(auto &j : used) j = LLONG_MAX;
used[v] = val;
if(check(v)) {
int cnt = 0;
for(auto &j : used) {
if(j == LLONG_MAX) continue;
cnt += abs(j);
}
if(cnt <= mn) {
mn = cnt;
for(int j = 0; j < used.size(); j ++) {
if(used[j] == LLONG_MAX) continue;
ans.push_back({j, used[j]});
}
}
}
// cout << val << " ";
// if(val == 0.5) {
// for(auto j : used) cout << j << " ";
// }
}
if(mn == LLONG_MAX) {
cout << "NO\n";
exit(0);
}
return ans;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
g.resize(n);
used.resize(n, LLONG_MAX);
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
int w;
cin >> w;
g[u].push_back({v, w*100});
g[v].push_back({u, w*100});
}
get_comps();
// assert(comp.size() < 2);
for(auto &j : used) j = LLONG_MAX;
vector <vector <pair <int,int>>> res;
for(auto i : comp) {
res.push_back(rec(i));
}
cout << "YES\n";
vector <int> ans(n);
for(auto i : res) {
for(auto j : i) ans[j.first] = j.second;
}
for(auto i : ans) cout << fixed << setprecision(6) << (double)i*0.01 << " ";
return 0;
}
Compilation message (stderr)
Graph.cpp: In function 'void get_comps()':
Graph.cpp:19:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < used.size(); i ++) {
| ~~^~~~~~~~~~~~~
Graph.cpp: In function 'std::vector<std::pair<long long int, long long int> > rec(long long int)':
Graph.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j = 0; j < used.size(); j ++) {
| ~~^~~~~~~~~~~~~
# | 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... |