#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
vector<pair<int,int>>v[maxn];
int marc[maxn], val[maxn], ja[maxn], sum, at, fim[maxn];
void concluir(int u){
ja[u]++;
for(pair<int,int> p : v[u]){
if(ja[p.first]) continue;
concluir(p.first);
}
}
void att(int u){
marc[u]=at;
fim[u]=val[u];
for(pair<int,int> p : v[u]){
if(marc[p.first]==at) continue;
att(p.first);
}
}
bool dfs(int u){
marc[u]=at;
sum+=abs(val[u]);
bool ok=true;
for(pair<int,int> p : v[u]){
int nxt=p.second-val[u];
if(marc[p.first]==at){
if(nxt!=val[p.first]) ok=false;
}else{
val[p.first]=nxt;
ok=(ok&dfs(p.first));
}
}
return ok;
}
void solve(){
int n, m; cin >> n >> m;
for(int i=1;i<=m;i++){
int a, b, c; cin >> a >> b >> c;
c*=2;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
for(int i=1;i<=n;i++){
if(!ja[i]){
int resp=inf;
for(int k=0;k<=100;k++){
sum=0;
at++;
val[i]=k;
if(dfs(i)){
if(sum<resp){
at++;
att(i);
resp=sum;
}
}
}
if(resp==inf){
cout << "NO" << endl;
return;
}
concluir(i);
}
}
cout << "YES" << endl;
for(int i=1;i<=n;i++){
double x=fim[i];
x/=2;
cout << x << " ";
}
cout << endl;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t=1; //cin >> t;
while(t--) solve();
}
# | 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... |