P6696

Purslane · 2022-05-20 22:53:18 · 题解

Solution

图论 ( ? )

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

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

当然我们会访问到一个已经确定过的点 , 设为 k_1 x + b_1 , 而现在应该是 k_2 x + b_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++ ! ( 垫底去喽 )