自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:23:10，当前版本为作者最后更新于2022-05-20 22:53:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

图论 ( ? )

考虑一个联通块里 , 如果确定一个数 , 那可以推导出其他所有的数 .

类似染色 , 这一个块中的第一个数设为 $x$ , 其他数推导出 $\pm x+k_i$ .

当然我们会访问到一个已经确定过的点 , 设为 $k_1 x + b_1$ , 而现在应该是 $k_2 x + b_2$ . 分类讨论 .

• $k_1 = k_2$ 且 $b_1 = b_2$ . 没有用是不是 . 直接 return .
• $k_1 = k_2$ 且 $b_1 \neq b_2$ . 显然无解 . 输出 NO .
• $k_1 \neq k_2$ . 可以解出 $x = -\frac{b_1 - b_2}{k_1-k_2}$ .

但我们有可能解不出来 $x$ . 然后化简就可以发现要求 $\sum |x-c_i|$ 的最小值 . 小学奥数题 , $x$ 为 $\{c\}$ 的中位数 .

注意 , 我们解出的 $x$ 可能不是合法解 . 回带的过程中看一下有没有矛盾 .

code :

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+20;
int n,m,flg,vis[MAXN],Vis[MAXN],k[MAXN],b[MAXN];
long double x,val[MAXN];
vector<pair<int,int>> G[MAXN];
vector<int> tmp;
void calc(int u,int K,int B) { //u:val=Kx+B
	if(vis[u]) {
		if(K==k[u]&&B!=b[u]) {cout<<"NO";exit(0);}
		if(K==k[u]&&B==b[u]) return ;
		flg=1,x=(b[u]-B)*1.0/(K-k[u]);
		return ;
	}
	vis[u]=1,k[u]=K,b[u]=B,tmp.push_back(-b[u]*k[u]);
	for(auto t:G[u]) {
		int to=t.first,w=t.second;
		calc(to,-K,w-B);
	}
	return ;
}
void fill(int u,long double x) {
	if(Vis[u]&&abs(x-val[u])>1e-7) {cout<<"NO";exit(0);}
	if(Vis[u]) return;
	val[u]=x,Vis[u]=1;
	for(auto t:G[u]) {
		int to=t.first,w=t.second;
		fill(to,w-x);
	}
	return ;
} 
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,m) {
		int a,b,c;cin>>a>>b>>c;
		G[a].push_back({b,c}),G[b].push_back({a,c});
	} 
	ffor(i,1,n) if(vis[i]==0) {
		flg=0,k[i]=1,b[i]=0,tmp.clear();
		calc(i,1,0);
		if(!flg) {
			sort(tmp.begin(),tmp.end());
			x=tmp[tmp.size()/2];
		}
		fill(i,x);
	}
	cout<<"YES\n";
	ffor(i,1,n) cout<<fixed<<setprecision(15)<<val[i]<<' ';
	return 0;
}

PKUSC RP++ ! ( 垫底去喽 )