chx一个蒟蒻来水本题第一篇题解
分析
首先不难发现一条边$(u,v,w)$表示的是一个方程 $x_u+x_v=w$ ，那么问题就转换为了方程组是否有解，求出绝对值最小解的问题
实现
首先图是不一定联通的，但因为每个连通块是独立的，所以可以分开处理。对于一个连通块如果存在唯一解，就把这个唯一解求出来，具体可以使用。
对于一个连通块存在多解，那么不妨设其中一个点的值为 $x$ 然后用 $±x+b$ 的方式把其他点值表示出来。然后再回到这个连通块对于答案的贡献：
$$\sum_{i=1}^{siz} \left\vert x-b_i\right\vert$$考虑绝对值之和的几何意义，可以把每个 $\left\vert x-b_i\right\vert$ 放到数轴上，显然让 $x$ 等于最中间的那一段（或者最中间的那一个点）的时候贡献最小，那么就排个序求出中间值即可
最后不要忘记用已知的那个点的值把其他点值推出来，整个算法的过程可以使用 pair<int,int>来实现。
代码
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))f^=(ch=='-'),ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=1e5+5,M=2e5+5;
const double eps=1e-6;
struct edge{
int to,p,w;
}d[M*2];
int last[N],cnt,n,m,vis[N],calc[N],sta[N],stop,mvp[N];
double ans[N];
pii coe[N];
map<pii,int> use;
void charu(int x,int y,int z){
d[++cnt]=edge{y,last[x],z};
last[x]=cnt;
}
void solve(int s){
coe[s]={1,0};
queue<int> que;
vis[s]=1;
que.push(s);
stop=0;
while(que.size()){
int u=que.front();
sta[++stop]=u;
que.pop();
for(int e=last[u];e;e=d[e].p){
int v=d[e].to,w=d[e].w;
pii ev={-coe[u].first,w-coe[u].second};
if(vis[v]){
if(ev==coe[v])continue;
if(ev.first==coe[v].first)exit(puts("NO")&0);
double uu;
uu=1.00*(coe[v].second-ev.second)/(1.00*(ev.first-coe[v].first));
if(!calc[s])ans[s]=uu,calc[s]=1;
else if(fabs(ans[s]-uu)>eps)exit(puts("NO")&0);
}
else{
vis[v]=1;
coe[v]=ev;
que.push(v);
}
}
}
if(!calc[s]){
for(int i=1;i<=stop;i++)
mvp[i]=-coe[sta[i]].second/coe[sta[i]].first;
sort(mvp+1,mvp+stop+1);
ans[s]=mvp[(stop+1)/2];calc[s]=1;
}
for(int i=2;i<=stop;i++){
ans[sta[i]]=coe[sta[i]].first*ans[s]+coe[sta[i]].second;
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
if(use[mpr(x,y)]){
if(use[mpr(x,y)]!=z)
exit(0&puts("NO"));
continue;
}
use[mpr(x,y)]=use[mpr(y,x)]=z;
charu(x,y,z),charu(y,x,z);
}
for(int i=1;i<=n;i++)if(!vis[i])solve(i);
puts("YES");
for(int i=1;i<=n;i++)printf("%lf ",ans[i]);
}
事实证明，码力很重要的