//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
#define int long long
#define double long double
const int N = 1e5 + 7;
const int inf = 1e9 + 7;
const double EPS = 0.000000000001;
const double INF = 1e9 + 7;
int n,m;
vector < pair < int , int > > graph[N];
pair < int , int > mem[N];//ax + b
int par[N];
int find(int a){
if(par[a] == a)return a;
return par[a] = find(par[a]);
}
void merge(int a , int b){
par[find(a)] = find(b);
}
void solve(){
cin >> n >> m;
iota(par , par + n + 1 , 0);
for(int i = 0;i<=n;i++)mem[i] = {inf , inf};
for(int i = 0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
graph[a].push_back({b , c});
graph[b].push_back({a , c});
merge(a,b);
}
int cnt_soln[n+1];
memset(cnt_soln , 0 , sizeof(cnt_soln));
double soln[n+1];
set < int > roots;
vector < int > components[n+1];
for(int i = 1;i<=n;i++){
roots.insert(find(i));
components[find(i)].push_back(i);
}
queue < pair < int , pair < int , int > > > q;
for(auto itr : roots){
q.push({itr , {1 , 0}});
}
while(sz(q)){
int node = q.front().first;
pair < int , int > eq = q.front().second;
q.pop();
if(mem[node] != pair < int , int >{inf , inf}){// check whether it matches or not
if(mem[node].first == eq.first and mem[node].second != eq.second){
cout << "NO" << endl;
return;
}
else if(mem[node].first == eq.first){
37;
}
else{
if(cnt_soln[find(node)]){
double mysoln = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first);
if(abs(soln[find(node)] - mysoln) > EPS)cnt_soln[find(node)]++;
}
else{
cnt_soln[find(node)]++;
soln[find(node)] = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first);
}
}
}
else{
mem[node] = eq;
// cout << "node " << node << " : " << eq.first << " " << eq.second << endl;
for(auto itr : graph[node]){
q.push({itr.first , {-eq.first , itr.second - eq.second}});
}
}
}
double ans[n+1];
for(auto itr : roots){
if(cnt_soln[itr] > 1){
cout << "NO" << endl;
return;
}
else if(cnt_soln[itr] == 1){
for(auto i : components[itr]){
ans[i] = mem[i].first * soln[itr] + mem[i].second;
}
}
else{
auto check = [&](double x){
double ret = 0;
for(auto i : components[itr]){
ret += abs((double)mem[i].first * x + (double)mem[i].second);
}
return ret;
};
double l = 0 , r = INF;
while(abs(l - r) > EPS){
double mid = (l + r) / 2;
if(check(mid) < check(mid + EPS)){
r = mid;
}
else{
l = mid + EPS;
}
}
for(auto i : components[itr]){
ans[i] = mem[i].first * l + mem[i].second;
}
}
}
cout << "YES" << endl;
for(int i = 1;i<=n;i++)cout << fixed << setprecision(6) << ans[i] << " ";
cout << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
Compilation message
Graph.cpp: In function 'void solve()':
Graph.cpp:62:5: warning: statement has no effect [-Wunused-value]
62 | 37;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
answer = YES |
| 2 |
Incorrect |
1 ms |
4956 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
answer = YES |
| 2 |
Incorrect |
1 ms |
4956 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
answer = YES |
| 2 |
Incorrect |
1 ms |
4956 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
answer = YES |
| 2 |
Incorrect |
1 ms |
4956 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
answer = YES |
| 2 |
Incorrect |
1 ms |
4956 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
