#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
const int MOD = 1e9;
/*
template<ll mod>
struct modnum {
static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
using S = conditional_t<is_big_mod, ll, int>;
using L = conditional_t<is_big_mod, __int128, ll>;
S x;
modnum() : x(0) {}
modnum(ll _x) {
_x %= static_cast<ll>(mod);
if (_x < 0) { _x += mod; }
x = _x;
}
modnum pow(ll n) const {
modnum res = 1;
modnum cur = *this;
while (n > 0) {
if (n & 1) res *= cur;
cur *= cur;
n /= 2;
}
return res;
}
modnum inv() const { return (*this).pow(mod-2); }
modnum& operator+=(const modnum& a){
x += a.x;
if (x >= mod) x -= mod;
return *this;
}
modnum& operator-=(const modnum& a){
if (x < a.x) x += mod;
x -= a.x;
return *this;
}
modnum& operator*=(const modnum& a){
x = static_cast<L>(x) * a.x % mod;
return *this;
}
modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};
using mint = modnum<MOD>;
template <class T> class SumSegmentTree {
private:
const T DEFAULT = 0;
vector<T> segtree;
int len;
public:
SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
void set(int ind, T val) {
ind += len;
segtree[ind] = val;
for (; ind > 1; ind /= 2) {
segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
}
}
T range_sum(int start, int end) {
T sum = DEFAULT;
for (start += len, end += len; start < end; start /= 2, end /= 2) {
if (start % 2 == 1) { sum += segtree[start++]; }
if (end % 2 == 1) { sum += segtree[--end]; }
}
return sum;
}
};
struct DSU{
vector<int> p, sz, used, mn, mx;
DSU(int n){
p.assign(n, 0);
sz.assign(n, 1);
used.assign(n, 0);
mx.assign(n, 0);
mn.assign(n, 0);
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int u){
if (p[u] == u) return u;
p[u] = find(p[u]);
return p[u];
}
void unite(int u, int v){
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
used[u] += used[v];
mn[u] = min(mn[u], mn[v]);
mx[u] = max(mx[u], mx[v]);
}
bool same(int u, int v){
return find(u) == find(v);
}
int size(int u){
u = find(u);
return sz[u];
}
};
const int N = 250005;
struct BIT {
ll b[N], n;
void init(int _n) {
n = _n ;
for(int i = 0 ; i <= n ; ++i) b[i] = 0;
}
inline int lowbit(int x) { return x & (-x); }
void update(int x, ll v) {
for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
}
ll query(int x) {
ll ans = 0;
for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
return ans;
}
} bit[2]; */
const float INF = 1e9;
int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}
int inv_ecd(int a, int m) {
int x, y;
int g = gcd(a, m, x, y);
if(g != 1) return -1;
x = (x + m) % m;
return x;
}
vector<vector<pi>>adjL;
map<int,int>ma;
vector<bool>vis;
vector<pi>val;
vector<float> ans;
bool FND;
float FND_X;
void set_ans(int pos) {
vis[pos] = 1;
for(pi adj: adjL[pos]) {
if(ans[adj.first] != INF) continue;
ans[adj.first] = adj.second - ans[pos];
set_ans(adj.first);
}
}
void dfs(int pos, int add, int sign, int prev) {
val[pos] = {add,sign};
vis[pos] = 1;
bool tmp1 = (add >= 0), tmp2 = (sign >= 0);
if(tmp1 == tmp2) ++ma[abs(add)];
else ++ma[-abs(add)];
for(pi adj: adjL[pos]) {
if(vis[adj.first]) {
if(adj.first == prev) continue;
if(val[adj.first].second == sign) {
FND = 1;
FND_X = (float)(adj.second - add - val[adj.first].first) / 2;
FND_X *= sign;
}
continue;
}
dfs(adj.first, adj.second - add, (sign == 1 ? -1 : 1), pos);
}
}
void solve() {
int n, m;
cin >> n >> m;
adjL.resize(n, vector<pi>());
vis.assign(n, 0);
val.resize(n);
ans.assign(n, INF);
vi V;
for(int i=0; i<m; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a, --b;
if(a == b) {
ans[a] = (float)c/2;
V.push_back(a);
continue;
}
adjL[a].push_back({b,c});
adjL[b].push_back({a,c});
}
for(int x: V) {
set_ans(x);
}
for(int i=0; i<n; ++i) {
if(vis[i]) continue;
ma.clear();
FND = 0;
dfs(i, 0, 1, i);
if(FND) {
ans[i] = FND_X;
set_ans(i);
continue;
}
ll L = 0, R = 0, mi, x, R2 = 0, L2 = 0;
int pos, prev;
for(auto it = ma.begin(); it != ma.end(); ++it) {
//cout << it->first << " - " << it->second << endl;
if(it == ma.begin()) pos = it->first, prev = it->second;
else {
R += it->second * (it->first - pos);
R2 += it->second;
}
}
mi = R;
x = (ma.begin())->first;
auto it = ma.begin();
++it;
for(; it != ma.end(); ++it) {
R -= (it->first - pos) * R2;
R2 -= it->second;
L2 += prev;
L += (it->first - pos) * L2;
prev = it->second;
pos = it->first;
if((L+R) < mi) {
mi = L+R;
x = it->first;
}
}
ans[i] = -x;
set_ans(i);
}
for(int i=0; i<n; ++i) {
for(pi adj: adjL[i]) {
if((ans[i] + ans[adj.first]) != adj.second) {
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
for(float x: ans) cout << x << " ";
cout << endl;
}
int main(){
//freopen("xortransform.in", "r", stdin);
//freopen("xortransform.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc = 1;
while (tc--) 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... |