#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;
vector<pair<bool,double>> val; // le teken de x(false = -1 ||true = 1) et b
vector<double> out;
double gem=0;
double gemC=0;
vector<vector<pair<int,int>>> neigh;
vector<int> visited;
double valeurDOFFICE=1e9;
bool possible=true;
void dfs(int x, bool tt, double b){
if(visited[x]==1){
if(val[x]==make_pair(tt,b)) return;
if(val[x].first==tt) { possible=false; return; }
else{
double b1=val[x].second;
double b2=b;
if(b1==false) swap(b1,b2);
valeurDOFFICE=(b1-b2)/(double)2;
return;
}
}
visited[x]=1;
val[x]={tt,b};
if(tt) gem+=-b;
else gem+=b;
gemC++;
for (auto u : neigh[x])
{
dfs(u.first,!tt,u.second-b);
if(possible==false||valeurDOFFICE<1e9){
return;
}
}
}
void setVAL(int x, double vl){
if(visited[x]==2){
if(abs(vl-out[x])>0.0000001) possible=false;
return;
};
out[x]=vl;
visited[x]=2;
for (auto u : neigh[x]) setVAL(u.first,u.second-vl);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,m; cin >> n >> m;
visited.resize(n,0);
neigh.resize(n);
out.resize(n);
val.resize(n);
for (int i = 0; i < m; i++)
{
int u,v,c; cin >> u >> v >> c; u--; v--;
neigh[u].push_back({v,c});
neigh[v].push_back({u,c});
}
for (int i = 0; i < n; i++)
{
if(visited[i]>0) continue;
gem=0;
gemC=0;
valeurDOFFICE=1e9;
dfs(i,true,0);
if(!possible) break;
if(valeurDOFFICE==1e9){
valeurDOFFICE=(gem)/gemC;
}
setVAL(i,valeurDOFFICE);
}
if(possible){
cout << "YES\n";
for (int i = 0; i < n; i++)
{
cout << setprecision(7) << out[i] << " ";
}
}else{
cout << "NO\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... |