Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double db;
- typedef pair<int,int> edge;
- typedef pair<ll,ll> node;
- const int maxn = 200001;
- bool vis[maxn];
- node val[maxn];
- db ans[maxn];
- vector<edge>G[maxn];
- bool flag, found;
- node x;
- const db eps = 1e-8;
- vector<int> cur;
- void dfs(int u, int p){
- vis[u] = 1;
- cur.push_back(u);
- for(auto v:G[u]){
- if(v.first == p) continue;
- node t = {val[u].first * -1ll, v.second - val[u].second};
- if(!vis[v.first]){
- val[v.first] = t;
- dfs(v.first, u);
- } else{
- if(t.first == val[v.first].first){
- if(t.second != val[v.first].second){
- flag = false;
- return;
- }
- } else{
- node tx = {t.first - val[v.first].first, val[v.first].second - t.second};
- if(!found) x = tx, found = 1;
- else if(x.first * tx.second != x.second * tx.first){
- flag = false;
- return;
- }
- }
- }
- }
- }
- db f(db xx){
- db res = 0;
- for(int u:cur)
- res += fabs(xx * (db)val[u].first + (db)val[u].second);
- return res;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- cout.setf(ios::fixed); cout.precision(7);
- int n, m;
- cin >> n >> m;
- while(m--){
- int u, v, c;
- cin >> u >> v >> c;
- G[u].push_back({v,c});
- G[v].push_back({u,c});
- }
- flag = true;
- for(int i = 1; i <= n && flag; i++)
- if(!vis[i]){
- val[i] = {1,0};
- found = false;
- cur.clear();
- dfs(i,-1);
- db xx = 0;
- if(found)
- xx = (db)x.second/(db)x.first;
- else{
- db l = -100000000, r = 100000000;
- while(fabs(r - l) > eps){
- db m1 = l + (r-l)/(db)3;
- db m2 = r - (r-l)/(db)3;
- if(f(m1) > f(m2))
- l = m1;
- else
- r = m2;
- }
- xx = l;
- }
- for(int u:cur)
- ans[u] = xx * (db)val[u].first + (db)val[u].second;
- }
- if(!flag){
- cout << "NO";
- return 0;
- }
- cout << "YES\n";
- for(int i = 1; i <= n; i++)
- cout << ans[i] << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement