#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> graph[100007];
bool odw[100007];
int tab1[100007];
int tab2[100007];
long double odp[100007];
int main()
{
int n, m;
cin >> n >> m;
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});
}
for (int i = 1; i <= n; i++)
{
if (!odw[i])
{
queue<int> q;
odw[i] = 1;
tab1[i] = 1;
tab2[i] = 0;
q.push(i);
vector<int> spojn;
spojn.push_back(i);
bool czyzdef = false;
int gdzie = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
for (auto x : graph[cur])
{
if (!odw[x.first])
{
odw[x.first] = 1;
tab1[x.first] = -tab1[cur];
tab2[x.first] = x.second - tab2[cur];
q.push(x.first);
spojn.push_back(x.first);
}
else
{
if (tab1[cur] + tab1[x.first] == 0)
{
if (tab2[cur] + tab2[x.first] != x.second)
{
cout << "NO" << endl;
return 0;
}
}
else
{
int gdzie2;
if(tab1[cur] + tab1[x.first] == 2)
{
gdzie2 = x.second - tab2[cur] - tab2[x.first];
}
else
{
gdzie2 = tab2[cur] + tab2[x.first] - x.second;
}
if (!czyzdef)
{
czyzdef = true;
gdzie = gdzie2;
}
else if (gdzie != gdzie2)
{
cout << "NO" << endl;
return 0;
}
}
}
}
}
long double x;
if (czyzdef)
{
x = (long double)gdzie / 2.0;
}
else
{
vector<long double> domed;
for (int y : spojn)
{
domed.push_back(-(long double)tab1[y] * (long double)tab2[y]);
}
sort(domed.begin(), domed.end());
if (domed.size() % 2 == 1)
{
x = domed[domed.size()/2];
}
else
{
x = (domed[domed.size()/2 - 1] + domed[domed.size()/2]) / 2.0;
}
}
for (int y : spojn)
{
odp[y] = (long double)tab1[y] * x + (long double)tab2[y];
}
}
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++)
{
cout << fixed << setprecision(10) << odp[i] << " ";
}
cout << endl;
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... |