Stavo risolvendo questo problema, un problema sui grafi bipartiti, e per evitare di utilizzare dei double, ho deciso di moltiplicare il peso di un arco per 2, tuttavia in questo modo 3 test case fallivano, mentre moltiplicando il peso dell’arco per 4 passa tutti i test case.
Ho letto l’editorial e anche da qua sembrerebbe che per trovare l’incognita il valore di un nodo venga diviso per 2.
Qua ci sono le due submission:
Ed ecco il codice (ho messo un commento nelle due uniche parti in cui i due codici differiscono):
#pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define reps(i,j,x) for(int i=(j);i<(x);i++)
#define repp(i,x) for(int i = 1; i <= (x); i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define maxint numeric_limits<int>::max()
#define minint numeric_limits<int>::min()
#define maxll numeric_limits<ll>::max()
#define minll numeric_limits<ll>::min()
#define nl '\n'
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef array<int, 3> i3;
typedef array<ll, 3> ll3;
typedef array<int, 4> i4;
typedef array<ll, 4> ll4;
typedef vector<i3> vi3;
typedef vector<ll3> vll3;
typedef vector<i4> vi4;
typedef vector<ll4> vll4;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
int nxt() {int x;cin >> x;return x;}
template <class T> void make_unique(T &arr) {sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());}
void print(){cout<<endl;} template <typename T, typename... Types> void print(T var1, Types... var2) {cout<<var1<<" ";print(var2...);}
template <typename T> T maxm(T var) {return var;} template <typename T, typename... Types> T maxm(T var1, Types... var2) {return max(var1,maxm(var2...));}
template <typename T> T minm(T var) {return var;} template <typename T, typename... Types> T minm(T var1, Types... var2) {return min(var1,minm(var2...));}
ll lpow(ll base, ll exp){ll result = 1;for (;;){if (exp & 1)result *= base;exp >>= 1;if (!exp)break;base *= base;}return result;}
int log2_floor(unsigned long long i) {return i ? __builtin_clzll(1) - __builtin_clzll(i) : 0;}
template <typename T> T maxv(vector<T> &var) {T maxi=numeric_limits<T>::min();for(auto x : var)maxi=max(maxi,x);return maxi;}
template <typename T> T minv(vector<T> &var) {T mini=numeric_limits<T>::max();for(auto x : var)mini=min(mini,x);return mini;}
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("balancing.in", "r", stdin);
#endif
//freopen("balancing.out", "w", stdout);
int t=1;
//cin>>t;
rep(i,t)solve();
}
void solve(){
int n,m;
cin>>n>>m;
vvpll adj(n+1);
rep(i,m){
int a,b,c;
cin>>a>>b>>c;
c*=2; // ------------------------------> cambiare il 2 in 4 fa 100 punti
adj[a].pb({c,b});
adj[b].pb({c,a});
}
vpll visited(n+1);
int poss=0;
repp(i,n)if(!visited[i].f){
vi st={i};
vll rem={0};
visited[i]={1,0};
bool found=0;
ll ans=-1;
while(!st.empty()&&!found&&poss!=-1){
int cur =st.back();
rem.pb(visited[cur].f*visited[cur].s*-1);
st.pop_back();
for(auto x : adj[cur]){
pll res = {visited[cur].f*-1,x.f-visited[cur].s};
if(!visited[x.s].f){
visited[x.s]=res;
st.pb(x.s);
}
else if(visited[x.s].f==res.f){
if(visited[x.s].s!=res.s){
poss=-1;
break;
}
}
else{
ans=(res.s-visited[x.s].s)/(visited[x.s].f-res.f);
found=true;
break;
}
}
}
if(ans==-1){
sort(all(rem));
ans=rem[rem.size()/2];
}
st={i};
visited[i]={2,ans};
while(!st.empty()&&poss!=-1){
int cur = st.back();
st.pop_back();
for(auto x : adj[cur]){
if(visited[x.s].f!=2){
visited[x.s]={2,x.f-visited[cur].s};
st.pb(x.s);
}
else if(visited[x.s].s!=x.f-visited[cur].s){
poss=-1;
break;
}
}
}
if(poss==-1)break;
}
if(poss==-1){
cout<<"NO"<<nl;
return;
}
cout<<"YES"<<nl;
repp(i,n)cout<<double(visited[i].s)/2<<" ";cout<<nl; //---------------------------> cambiare il 2 in 4 fa 100 punti
}