제출 #958130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958130		kanpham	Graph (BOI20_graph)	C++14	0 / 100	2 ms	4188 KiB

Graph

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int MAX = 1e5+2;
const double err = 1e-6;

int n;
vector<array<int,2>> g[MAX];
bool vis[MAX];
double ans[MAX];
complex<int> linear[MAX];

void sakujo(){
    cout << "NO";
    exit(0);
}

vector<int> hist;
double key;
void dfs(int s){
    vis[s] = true;
    hist.push_back(s);

    for (auto e:g[s]){
        int v = e[0];
        complex<int> sum = {e[1], 0};
        if (vis[v]){
            int a1 = linear[v].real(), a2 = linear[s].real(), b1 = linear[v].imag(), b2 = linear[s].imag();
            if (b1 + b2 == 0){
                if (a1 + a2 == e[1]) continue;
                sakujo();
            }
            key = ((double)e[1] - a1 - a2) / ((double)b1 + b2);
            continue;
        }
        linear[v] = sum - linear[s];
        dfs(v);
    }
}

void calc(int s, double val){
    vis[s] = true;
    ans[s] = linear[s].real() + linear[s].imag() * val;

    for (auto e:g[s]){
        int v = e[0];
        if (!vis[v]) calc(v, val);
    }
}

void verify(int s){
    vis[s] = true;
    for (auto e:g[s]){
        int v = e[0];
        double sum = e[1];
        if (abs(ans[s] + ans[v] - sum) > err) sakujo();
        if (!vis[v]) verify(v);
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

   

    int m;
    cin >> n >> m;
    while (m--){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    for (int i=1; i<=n; ++i){
        if (!vis[i]){
            hist.clear();
            linear[i] = {0, 1};
            dfs(i);

            for (int v:hist) vis[v] = false;
            calc(i, key);

            for (int v:hist) vis[v] = false;
            verify(i);
        }
    }

    cout << "YES\n" << setprecision(6);
    for (int i=1; i<=n; ++i) cout << ans[i] << ' ';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42