#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
void solve() {
int n, m;
cin >> n >> m;
vector <vector <pair <int, double>>> graph(n+1);
vector <pair <pii, double>> edges;
for (int i = 1; i <= m; i++) {
int a, b;
double c;
cin >> a >> b >> c;
edges.pb(mp(mp(a, b), c));
graph[a].pb(mp(b, c));
graph[b].pb(mp(a, c));
}
const int range = 301;
vector <vector <bool>> can(n+1, vector <bool> (range, 1));
vector <vector <double>> value(n+1, vector <double> (range)), sum(n+1, vector <double> (range));
vector <pair <double, int>> acc(n+1, mp(2e9, 0));
vector <int> link(n+1), saizu(n+1, 1);
iota(all(link), 0);
function <int(int)> find = [&](int n) {
if (link[n] == n) return n;
return link[n] = find(link[n]);
};
function <void(int, int)> unite = [&](int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (saizu[a] < saizu[b]) swap(a, b);
saizu[a] += saizu[b];
link[b] = a;
};
for (auto to : edges) {
auto a = to.first.first, b = to.first.second;
unite(a, b);
}
vector <int> used(n+1);
function <void(int, double, int)> dfs = [&](int v, double val, int i) {
value[v][i] = val;
used[v] = 1;
for (auto to : graph[v]) {
if (used[to.first]) continue;
dfs(to.first, to.second-val, i);
}
};
set <int> reps;
for (int i = 1; i <= n; i++) reps.insert(find(i));
for (int j = 0; j < 200; j++) {
auto ran = rand()%1001;
for (int i = 1; i <= n; i++) {
if (i == find(i)) {
dfs(i, (ran-500)*.1, j);
}
}
for (int i = 1; i <= n; i++) {
sum[find(i)][j] += fabs(value[i][j]);
}
for (auto to : edges) {
auto a = to.first.first, b = to.first.second;
auto c = to.second;
auto rep = find(a);
if (fabs(c-value[a][j]-value[b][j]) > 1e-9) {
can[rep][j] = 0;
}
}
fill(all(used), 0);
for (auto to : reps) {
if (can[to][j]) {
if (acc[to].first > sum[to][j]) {
acc[to].first = sum[to][j];
acc[to].second = j;
}
}
}
}
double ans = 0;
for (auto to : reps) {
ans += acc[to].first;
}
if (ans >= 2e9) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++) {
cout << fixed << setprecision(6) << value[i][acc[find(i)].second] << ' ';
}
}
int main() {
//~ do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
7
4 2
5 7
3 4
6 3
1 3
4 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
